In this paper we study the problem of simulating shared memory on the distributed memory machine (DMM). Our approach uses multiple copies of shared memory cells, distributed among the memory modules of the DMM via universal hashing. The main aim is to design strategies that resolve contention at the memory modules. Extending results and methods from random graphs and very fast randomized algorithms, we present new simulation techniques that enable us to improve the previously best results exponentially. In particular, we show that an n-processor CRCW PRAM can be simulated by an n-processor DMM with delay $\O(\log\log\log n \log^*n)$, with high probability. Next we describe a general technique that can be used to turn these simulations into time-processor optimal ones, in the case of EREW PRAMs to be simulated. We obtain a time-processor optimal simulation of an (n log log log n log * n )-processor EREW PRAM on an n-processor DMM with delay $\O(\log\log\log n \log^*n)$, with high probability. When an (n log log log n log * n )-processor CRCW PRAM is simulated, the delay is only by a log * n factor larger. We further demonstrate that the simulations presented can not be significantly improved using our techniques. We show an $\Omega(\log\log\log n / \log\log\log\log n)$ lower bound on the expected delay for a class of PRAM simulations, called topological simulations, that covers all previously known simulations as well as the simulations presented in the paper.

Many applications of fast Fourier transforms (FFTs), such as computer tomography, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveals that the usual method of fixed-point computation of FFTs of vectors of length 2/sup l/ leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real-time applications. Several researchers have noted that calculation of FFTs with algebraic integers avoids computational noise entirely. We combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorithm to compute b-bit precision FFTs of length L. More precisely, we approximate complex numbers by cyclotomic integers in Z[e(2/spl pi/i/2/sup n/)] whose coefficients, when expressed as polynomials in e(2/spl pi/i/2/sup n/), are bounded in absolute value by some integer M. For fixed n our algorithm runs in time O(log(M)), and produces an approximation with worst case error of O(1/M(2/sup n-2/-1)). We prove that this algorithm has optimal worst case error by proving a corresponding lower bound on the worst case error of any approximation algorithm for this task. The main tool for designing the algorithms is the use of the cyclotomic units, a subgroup of finite index in the unit group of the cyclotomic field. First implementations of our algorithms indicate that they are fast enough to be used for the design of low-cost high-speed/high-precision FFT chips.

We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-line and without using a global controller. Traditionally, the main aim of allocation processes is to place the balls into bins to minimize the maximum load in bins. However in many applications it is equally important to minimize the number of trails performed by the balls (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We investigate allocation processes that may reallocate the balls. We provide a tight analysis of the maximum load of processes that during placing a new ball may reassign the balls in up to d randomly chosen bins. We study infinite processes, in which in each step a random ball is removed and a new ball is placed according to some scheduling rule. We present a novel approach that establishes a tight estimation of the time needed for the infinite process to be in the state near to its equilibrium. Finally, we provide a tight analysis of the maximum load of the off-line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on-line load balancing processes.

Many applications of fast fourier transforms (FITs), such as computer-tomography, geophysical signal processing, high resohstion imaging radars, and prediction filters, require high precision output.The usual method of fixed point computation of FIT's of vectors of length 21 leads to an average loss of f/2 bits of precision.This phenomenon, often referredto as computationalnoise, causes major problems for arithmeticunits with limited precision which areoften used for real time applications.Severalresearchers have noted thatcalculation of ITT's with algebraic integersavoids computationalnoise entirely,see, e.g., [3].We will show thatcomplex numbers can be approximated accurately by cyclotomic integers, andcombine this idea with Chinese remainderingstmtegiesin the cyclotomic integersto, rotsgbly,give a O(b'" L log( L) ) algorithm to compute b-bit precision FIT's of length L. The firstpart of the paperwill describe the ~strategy,assuminggood approximationalgorithms;the second partpresentsanew, general,andefticient algorithmfor a~proximatingcomplex numbersby cyclotomic integersin Z[e2*'\2 ] whose coefficients, when expressedas polynomials in e'~ii'", are bounded in absolute value by some integer M. For fixed n our algorithm runs in time 0(log(A4)), and produces an approximation with worst case errorof 0(1/A42"-2'1).We will prove that this algorithm has optimal worst case emor by proving a correspondinglower bound on the worstcase errorof any approximationalgorithm for this task.Firstimplementationsof our algorithmsindicate thatthey are fast enough to be used for the design of low cost high speecfhigh precision FIT-chips.

Abstract | We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for these codes have fast and simple software implementations. Implementations of our algorithms are faster by orders of magnitude than the software implementations of previous algorithms. We expect these codes will be extremely useful for applications where lossy channels are common and fast decoding is a requirement, e.g., satellite transmission and multicast transmission over the Internet. I.

We study the well known problem of throwing m balls into n bins.If each ball in the sequential O(log log n).