The subject of I/O has often been neglected in the design of parallel computersystems, although for many problems I/O rates will limit the speedup attainable. The I/O problem is addressed here by considering the role...
详细信息
ISBN:
(纸本)0897913418
The subject of I/O has often been neglected in the design of parallel computersystems, although for many problems I/O rates will limit the speedup attainable. The I/O problem is addressed here by considering the role of files in parallel systems. The notion of parallel files is introduced. Parallel files provide for concurrent access by multiple processes, and utilize parallelism in the I/O system to improve performance. Parallel files can also be used conventionally by sequential programs. A set of standard parallel file organizations is proposed, based on common data partitioning techniques. Implementation strategies for the proposed organizations are suggested, using multiple storage devices. Problem areas are also identified and discussed.
The authors classify synchronization schemes based on how synchronization variables are used. A scheme called the process-oriented scheme is proposed. This scheme requires a very small number of synchronization variab...
详细信息
ISBN:
(纸本)9780897913195
The authors classify synchronization schemes based on how synchronization variables are used. A scheme called the process-oriented scheme is proposed. This scheme requires a very small number of synchronization variables and can be supported very efficiently by simple hardware in the system.
An assignment problem is discussed, using the concept of stable marriage assignment to solve the multifunction assignment problem for unequal sets. The method divides the problems into different levels and gives an ap...
详细信息
ISBN:
(纸本)0929029301
An assignment problem is discussed, using the concept of stable marriage assignment to solve the multifunction assignment problem for unequal sets. The method divides the problems into different levels and gives an approach for multifunction matching. An example of assigning courses to professors is used to explain the nature of the problems involving multifunction assignment.
Definitions and properties of a complete binary tree and a binary search tree are well known. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a ...
详细信息
ISBN:
(纸本)0897912993
Definitions and properties of a complete binary tree and a binary search tree are well known. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a tree a Complete Binary Search Tree, a CBS Tree for short. Two basic advantages of a CBS tree are that it is a search tree with minimum height and that it can be placed in an array. The latter allows for implementation of the data structure without the use of pointers.
A new single-block implementation which is more robust than Rudolph's network and needs no redundancy or external permuters is introduced. The authors consider a class of single-stage designs with redundancy and c...
详细信息
ISBN:
(纸本)0929029301
A new single-block implementation which is more robust than Rudolph's network and needs no redundancy or external permuters is introduced. The authors consider a class of single-stage designs with redundancy and compare the characteristics of networks discussed. It is shown that with area reduction and improved fault-tolerance, the new single-block layout has only a small constant factor time increase, although the two-stage-layout may require less time to sort in the presence of comparator failures.
It is noted that lookup table implementations of a square root are very inefficient in terms of hardware, while algorithmic techniques are inefficient in terms of speed. The author considers square-root implementation...
详细信息
It is noted that lookup table implementations of a square root are very inefficient in terms of hardware, while algorithmic techniques are inefficient in terms of speed. The author considers square-root implementations combining both techniques, which are a compromise between speed and complexity. The proposed technique speeds up the algorithmic implementation by using a PLA (programmable logic array) lookup table to determine both the MSBs (most significant bits) of the square root and the square of these bits. The square is subtracted from the original number to obtain a partial remainder, and the remaining square-root bits are determined algorithmically.
External sorting is frequently used by relational database systems for building indexes on tables, ordered retrieval, duplicate elimination, joins, subqueries, grouping, and aggregation;it would be quite beneficial to...
详细信息
External sorting is frequently used by relational database systems for building indexes on tables, ordered retrieval, duplicate elimination, joins, subqueries, grouping, and aggregation;it would be quite beneficial to parallelize this function. Previous parallel external sorting algorithms found in the database literature used a sequential merge as the final stage of the parallel sort. This reduces the speedup gained through parallelism in earlier stages of sort. The solution is to merge in parallel as well. Load balanced parallel two way merges and approximately load balanced parallel multi way merges are known. Measurements reported on parallel sorting that employs one of the approximate partitioning methods indicate that even if the sort keys are randomly distributed the load imbalance due to the approximation degrades speedup due to parallelism. Sort key value skews, known to occur in database workloads, can only exacerbate this problem. We give, prove and analyze an efficient exact method which can find any percentile of an arbitrary number of sorted runs.
Assume that uniform hashing is used to post items into a table with m rows. For any n such that 0 ≤ n n,m represent the expected number of probes needed to post the (n + 1)st item. Clearly, E0,m = 1 for any m ≥ 1. F...
详细信息
ISBN:
(纸本)0897912993
Assume that uniform hashing is used to post items into a table with m rows. For any n such that 0 ≤ n n,m represent the expected number of probes needed to post the (n + 1)st item. Clearly, E0,m = 1 for any m ≥ 1. For n > 0, posting the (n + 1)st item will require only one probe if its key hashes to an open address, and the probability of this is (m-n)/m. Otherwise, with probability n/m, the (n + 1)st key will hash to an occupied address, so the number of probes required is one plus the number of probes required in the rest of the table. But since that occupied address will not be accessed in subsequent probes, the expected number of probes in the rest of the table is the same as the expected number of probes to post an nth item in a table of size m-1.
An improved implementation of the rebound sorter of T. C. Chen et al. (IEEE Proc. 4th Conf. of Very Large Databases, pp. 312-318, Sept. 1978) is described. The pipelining technique chosen is unique to this design. A s...
详细信息
An improved implementation of the rebound sorter of T. C. Chen et al. (IEEE Proc. 4th Conf. of Very Large Databases, pp. 312-318, Sept. 1978) is described. The pipelining technique chosen is unique to this design. A single rebound sorting chip can sort eight 16-b records. By connecting these chips in a chain, it is possible to sort more than eight records. The VLSI version of the rebound sorter described in this paper is also simpler and smaller than many other sorters discussed in the literature. The Genesil silicon compiler, a commercial CAD tool, was used to implement the chip.
A non-preemptive deadlock-free concurrency control mechanism based on extendible hashing has been presented for main memory database system. The algorithm makes use of the verification process of the optimistic concur...
详细信息
ISBN:
(纸本)0897912993
A non-preemptive deadlock-free concurrency control mechanism based on extendible hashing has been presented for main memory database system. The algorithm makes use of the verification process of the optimistic concurrency control algorithm and two-phase locking policy to manage concurrent operations on sharable data. We also present a comparison of our algorithm with other two-phase locking mechanisms and show that our algorithm is more robust, easier to implement and provides a higher degree of concurrency than other algorithms on extendible hash file.
暂无评论