A VLSI sorter of size O(n) can sort n elements in linear time when the input and output time are taken into account. If the input contains more than n elements, some preprocessing has to be performed. A VLSI partition...
详细信息
A VLSI sorter of size O(n) can sort n elements in linear time when the input and output time are taken into account. If the input contains more than n elements, some preprocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner is O(log k) for a data file of size kn where n is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must go O(k) times through the partitioner as in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.
We consider a recursive sorting algorithm in which, in each invocation, a new variable and a new procedure (using the variable globally) are defined and the procedure is passed to recursive calls. This algorithm is pr...
详细信息
We consider a recursive sorting algorithm in which, in each invocation, a new variable and a new procedure (using the variable globally) are defined and the procedure is passed to recursive calls. This algorithm is proved correct with Hoare-style pre- and postassertions. We also discuss the same algorithm expressed as a functional program.
作者：
KUNDE, MUNIV KIEL
INST INFORMAT & PRAKT MATH D-2300 KIEL 1 FED REP GER
Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting N=n1 n 2...n r elements on an n 1×n2×... ×n r array 2(n 1+...+n r?1)+n r data interchange steps are needed asym...
详细信息
Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting N=n1 n 2...n r elements on an n 1×n2×... ×n r array 2(n 1+...+n r?1)+n r data interchange steps are needed asymptotically. For two dimensions these bounds are asymptotically best possible provided that n 1 and n 2 are powers of 2. In this case the generalized s 2-way merge sort of Thompson and Kung turns out to be asymptotically optimal. The minimal asymptotic bound of 2 √2N interchange steps can be obtained only by sorting algorithms suitable for √N/2×√2N meshes. For r≧3 dimensions an analysis of aspect-ratios also demonstrates that there exist mesh-connected architectures which are better suited for sorting than simple r-dimensional cubes.
The paper describes a methodology for the structured description of a distributed program, and its implementation within XMDS, a programming environment for the development of multiprocessor applications. Such program...
详细信息
The paper describes a methodology for the structured description of a distributed program, and its implementation within XMDS, a programming environment for the development of multiprocessor applications. Such programs are composed by a set of concurrent processes, each one consisting of separately compilable modules. The method is compared with those of Ada and Modula-2; the implementation is compared with the approach followed in the design of another programming environment for multimicros.
We present a simple deterministic parallel algorithm that runs on a CRCW PRAM and sorts n integers of size polynomial in n in time O(log n) using O(n log log nlog n) processors. It is closer to optimality than any pre...
详细信息
We present a simple deterministic parallel algorithm that runs on a CRCW PRAM and sorts n integers of size polynomial in n in time O(log n) using O(n log log nlog n) processors. It is closer to optimality than any previously known deterministic algorithm that solves the stated restricted sorting problem in polylog time.
The specification language Z (“zed”), based on set theory, has been used to define a microprocessor based system in a formal notation. The 8-bit Motorola 6800 was chosen as an example because of its simplicity. Memo...
详细信息
The specification language Z (“zed”), based on set theory, has been used to define a microprocessor based system in a formal notation. The 8-bit Motorola 6800 was chosen as an example because of its simplicity. Memory configuration and interrupts were included. This paper presents parts of this specification. The use of a formal description language allows the possibility of verification of the instruction set. Z could also be used at the design stage. Additionally, the use of Z combined with informal text is sufficently readable for the specification to be used for documentation purposes. With the experience gained, a more complicated or a completely new microprocessor could now be attempted.
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 ).
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).
Several variants of quicksort are compared in order to find an efficient internal sorting algorithm for sorting large files in a virtual memory environment. The algorithms compared are original quicksort; ‘Esort’, w...
详细信息
Several variants of quicksort are compared in order to find an efficient internal sorting algorithm for sorting large files in a virtual memory environment. The algorithms compared are original quicksort; ‘Esort’, which uses a fixed memory partition of two page frames; ‘Wsort’, which combines quicksort with merging and sorts one page at a time to reduce page fetches; and ‘Psort’, which uses manual replacement of pages guided by estimates of the interval to the next reference. The comparison is based on several sorting runs on different-size random-ordered files. A memory management simulator with fetch on demand and working set replacement strategy is used to achieve performance measures: the total execution time, the main memory space allocation, and the main memory space-time *** achieves its best performance with a relatively small page size and a very small window size. Reducing page faults by increasing the window size results in excessive space allocation. In an optimal environment, Psort gives some 30-40% smaller space-time integral than quicksort. The space allocation sizes are close to each other, but Psort needs less that half of the page fetches of quicksort. The results for Esort are close to those of quicksort. Wsort does not compete favourably with the original quicksort. In a typical virtual memory environment with a large page size and a large window size, both Esort and Psort perform remarkably better than original quicksort. The space-time integral difference of Psort and quicksort is over 50%, and it increases with an increasing file size.
systems in which multiple users share hardware resources are considered. Local area networks, internal networks (multiple single-board computers in a chassis), and networks of multiuser clusters are used as solutions ...
详细信息
systems in which multiple users share hardware resources are considered. Local area networks, internal networks (multiple single-board computers in a chassis), and networks of multiuser clusters are used as solutions for information systems problems. However, as the number of multiuser options available increases, so does the number of problems caused by software never meant for use in a multiuser environment. It is shown how MS-DOS 3. 1 gives limited support to file sharing via networks. There is a command, SHARE, that lets the programmer specify a filename to be shared, buffer space for the shared file, and number of locks to be supported for that file. This information must be specified for each file that is to be shared over the network. The opening of files in various modes is then accomplished with an operating system call.
暂无评论