Proof methods adequate for computer programs expressed in a wide range of languages are well developed. One program construct, however, has been neglected—namely, that of decision tables. It is shown here how decisio...
详细信息
Proof methods adequate for computer programs expressed in a wide range of languages are well developed. One program construct, however, has been neglected—namely, that of decision tables. It is shown here how decision table programs can be proved correct. The use of theirlevelstructure and the treatment of ‘impossible’ rules are of special significance. The method is illustrated by a proof of a bubble sort algorithm.
This paper discusses the possible role of computer software within computersystems design. A widely-publicised, automatic method (ISDOS's SODA) is critically evaluated and an alternative, computer-aided method (C...
详细信息
This paper discusses the possible role of computer software within computersystems design. A widely-publicised, automatic method (ISDOS's SODA) is critically evaluated and an alternative, computer-aided method (CAM's CAD) is proposed.
A dynamical system called a bubbling system is formulated, and the configurations of the system are characterized by a function POTENTIAL . We show that the number of steps for a given bubbling system B to reach its e...
详细信息
A dynamical system called a bubbling system is formulated, and the configurations of the system are characterized by a function POTENTIAL . We show that the number of steps for a given bubbling system B to reach its equilibrium configuration from its configuration at the t th step is evaluated by POTENTIAL ( B, t ).
Efficient multiprogram processing algorithms are proposed for operations scheduling the loading of independent and data-related multivolume-data processing jobs.
Efficient multiprogram processing algorithms are proposed for operations scheduling the loading of independent and data-related multivolume-data processing jobs.
History has taught that the design and implementation of an efficient parallel simulation program is a tedious and error prone process. Methods that can circumvent the parallelization steps in this process are usually...
详细信息
History has taught that the design and implementation of an efficient parallel simulation program is a tedious and error prone process. Methods that can circumvent the parallelization steps in this process are usually warmly welcomed by parallel simulation architects. In this paper we introduce a Parallel Cellular Automata Modeling, environment (P-CAM) for doing spatial load balancing on arbitrary connected grids or task graphs. This environment adopts an object oriented application framework in which we can instantiate a variety of simulation problems. We have implemented a kernel, based on this framework, which facilitates dynamic load balancing and supports process migration and irregular interprocess communication patterns. The design of the kernel enables a transparent implementation of complex systems models onto arbitrary parallel computersystems. We show that the design of a parallel simulation program can be assisted by using the P-CAM kernel. (C) 1999 Elsevier Science B.V. All rights reserved.
A multi-channel broadcast network is a distributed computation model in which p independent processors communicate over a set of p shared broadcast channels. Computation proceeds in synchronous cycles, during each of ...
详细信息
A multi-channel broadcast network is a distributed computation model in which p independent processors communicate over a set of p shared broadcast channels. Computation proceeds in synchronous cycles, during each of which the processors first write and read the channels, then perform local computations. Performance is measured in terms of the number of cycles used in the computation, where each bit to be transmitted is assumed to require a separate cycle. In this paper we investigate the problem of sorting p bit strings of uniform length m , each string initially located at a different processor in the broadcast network. We develop an efficient sorting method that first reduces the length of the strings without affecting their relative order, then proceeds using only the shorter strings. A sequence of three successively improved algorithms based on this approach is presented, the best of which runs in O( m + p log p ) cycles. By showing a lower bound of Ω( m ) cycles, we prove that the algorithm is optimal for sufficiently large m . Our results improve by a factor of log p the solution of the multiple identification problem presented by Landau, Yung and Galil (1985).
HyperNet is an authoring and browsing system facilitating creation and navigation of multimedia documents. It is conceived and designed to provide a mechanism for very fast choreographing and configurating of hypermed...
详细信息
HyperNet is an authoring and browsing system facilitating creation and navigation of multimedia documents. It is conceived and designed to provide a mechanism for very fast choreographing and configurating of hypermedia documents. This system provides to the users a hypermedia integration and browsing environment to document component databases distributed across the world, provided they have access to the Internet network and are valid HyperNet sites. The intention was for users to be able to search for and retrieve documents stored locally and/or remotely, while the access mechanism being completely transparent. This system was implemented and tested with a suite of hypermedia document components which were distributed over southern California and Europe.
A parallel version of quicksort on a CRCW PRAM is developed. The algorithm uses n processors and a linear space to sort n keys in the expected time O (log n ) with large probability.
A parallel version of quicksort on a CRCW PRAM is developed. The algorithm uses n processors and a linear space to sort n keys in the expected time O (log n ) with large probability.
In his survey paper on branching programs, Razborov asked the following question: Does every rectifier-switching network computing the majority of n bits have size n(1+Omega(1))? We answer this question in the negativ...
详细信息
In his survey paper on branching programs, Razborov asked the following question: Does every rectifier-switching network computing the majority of n bits have size n(1+Omega(1))? We answer this question in the negative by constructing a simple oblivious branching program of size O[n log(3) n/log log n log log log n] for computing any threshold function. This improves the previously best known upper bound of O(n(3/2)) due to Lupanov. We also construct oblivious branching programs of size o(n log(4) n) for computing general mod functions. All previously known constructions for computing general mod functions have size Omega(n(3/2)). (C) 1997 Academic Press.
作者：
LOMET, DBIBM CORP
THOMAS J WATSON RES CTREXPTL COMPILING SYST GRPYORKTOWN HTSNY 10598
A storage management scheme is described that supports the invalidation of addresses to freed storage and thus, in that sense, provides a secure system. Unlike previous virtual memory techniques, the allocated areas o...
详细信息
A storage management scheme is described that supports the invalidation of addresses to freed storage and thus, in that sense, provides a secure system. Unlike previous virtual memory techniques, the allocated areas of our scheme can vary from the very large, requiring multiple pages of storage, to the very small, in which several can be contained on a single page. Special treatment is accorded procedure activation storage so as to provide increased effectiveness for this important case. The interaction of this deletion scheme with garbage collection techniques is also examined. Finally, the relative advantages of retention and deletion strategies of storage management are considered.
暂无评论