In the quest to build exascale supercomputers, designers are increasing the number of hierarchical levels that exist among system components. Software developed for these systems must account for the various hierarchi...
详细信息
ISBN:
(纸本)9783642244483
In the quest to build exascale supercomputers, designers are increasing the number of hierarchical levels that exist among system components. Software developed for these systems must account for the various hierarchies to achieve maximum efficiency. The first step in this work is to identify groups of processes that share common resources. We develop, analyze, and test several algorithms that can split millions of processes into groups based on arbitrary, user-defined data. We find that bitonic sort and our new hash-based algorithm best suit the task.
Deletions in open addressing hash tables are often handled by marking the cells as "deleted" instead of "empty", because otherwise the search algorithm might fail to find some of the keys. The spac...
详细信息
Deletions in open addressing hash tables are often handled by marking the cells as "deleted" instead of "empty", because otherwise the search algorithm might fail to find some of the keys. The space used by deleted cells may be reused by subsequent insertions. Intuitively, search times should deteriorate as tables become contaminated with deleted cells and, as Knuth points out, in the long run the average successful search time should approach the average unsuccessful search time. We analize the effect of a long sequence of deletions and insertions over tables that use one of three insertion disciplines: standard "first-come-first-served" (FCFS)[2], "last-come-first-served" (LCFS) [3] and "Robin Hood" (RH)[1]. We show that deletions have the predicted effect over the average search cost, but their effect over the variance differs according to the insertion discipline used. When no deletions are allowed, FCFS has a very dispersed distribution, while those of LCFS and RH are very concentrated. But we show that, after many deletions and insertions, both FCFS and LCFS approach a common steady state with high dispersion, while the distribution of RH remains concentrated. We also study the transient behaviors of these methods, doing both an asymptotic and an exact analysis.
We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about...
详细信息
We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.
The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hash...
详细信息
The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store.
暂无评论