Parallel hashing is well-known in the folklore of parallel computing, but there has been a remarkable dearth of literature describing it in detail. Because many parallel algorithms such as histogramming, set intersection and dictionary lookup can make use of hashing as a core step, hashing is a fundamental parallel operation. This paper sheds light on the performance that may be achieved using parallel hashing algorithms and should lend credibility to their use.

For a sequence of n values, each with an associated integer label, the multiprefix operation calculates a partial sum for each value summing all preceding values with the same label, and for each label, a reduction value summing all values with that label.The multiprefix operation has been proposed as a parallel primitive because of its power for expressing many data parallel algorithms succinctly.However, most approaches to implementing this operation have been based on speciat hardware, limiting its usefulness.This paper presents an algorithm for the multiprefix operation on n elements that runs in S = 0(W) parallel steps on a p = @ processor CRCW-ARBITRARY PRAM.Because this algorithm performs only W = O(n) work, it is work efficient.While approaches based on sorting could be implemented in asymptotically fewer parallel steps, the work efficiency of this algorithm, and its low overhead make it attractive for use in real applications.A fully vectorized version of this algorithm has been designed for the CRAY Y-MP and provides good performance for a number of important algorithms.Performance data collected from integer sorting and sparse matrix-vector multiplication benchmarks based on the multiprefix operation achieve speeds that are often better than currently employed algorithms for that machine.

The COSMOS simulator provides fast and accurate switch-level modeling of MOS digital circuits. It attains high performance by preprocessing the transistor network into a functionally equivalent Boolean representation. This description, produced by the symbolic analyzer ANAMOS, captures all aspects of switch-level networks including bidirectional transistors, stored charge, different signal strengths, and indeterminate (X) logic values. The LGCC program translates the Boolean representation into a set of machine language evaluation procedures and initialized data structures. These procedures and data structures are compiled along with code implementing the simulation kernel and user interface to produce the simulation program. The simulation program runs an order of magnitude faster than our previous simulator MOSSIM II.