Extremely parallel algorithms

The parallel computer, believed to play a key role in upcoming high-speed computer systems, consists of two or more processors and a communication facility connecting them. The communication facility can be the shared memory to which all the processors can access commonly or several types of networks such as the mesh connection and the cube connection. This article surveys recent progress of computer algorithms on those parallel computers. Especially, attentions are focused on ‘extremely’ parallel algorithms, i.e., they assume that greatly many processors are available. For example, sorting of n items can be carried out in nlogn steps sequentially (using a single processor) but only logn steps are enough if we can use n processors. Namely we can speed up n times by n processors. The survey mainly introduces principal techniques useful under this kind of parallel environment. [In Japanese.]