Titlebook: Parallel and Distributed Computing: Theory and Practice; Theory and Practice. Michel Cosnard,Afonso Ferreira,Joseph Peters Conference proce

figurine

哀悼

The parallel complexity of algorithms for pattern formation models, results represent one of the first applications of the tools of parallel computational complexity theory to complex physical systems. The specific models we study are ., and .. It is known that all of these processes yield complex, fractal patterns. The paper shows that decision problems based on f

dermatomyositis

predict

Embedding 3-dimensional grids into optimal hypercubes,rcube with a small constant communication overhead. We introduce new easily computable functions which embed many 3-dimensional grids into their optimal hypercubes with dilation 2. Moreover, we show that one can reduce the open problem to recognize whether it is possible to embed every 3-dimensional

Ophthalmoscope

Distributed cyclic reference counting,ment of lazy mark-scan. The algorithm allows processors to run local mark-scan simultaneously without any need of synchronisation between phases of different local mark-scans either on the same processor or on different processors.

atopic

Efficient reconstruction of the causal relationship in distributed systems,. The initial algorithm dealing with reconstruction of the causal past of given events is greatly improved. We show a greedy algorithm whose complexity is O(S.) where . is the number of processes involved in the system. Furthermore, distributed implementation of our algorithm is optimal since it use

史前

Sorting and selection on arrays with diagonal connections,r selection by making use of the diagonal connections. In particular, on an . mesh with diagonal connections, we show how to select the .-th largest of .. elements in 0.65. steps, and on a torus in 0.59. steps. The best known results for the corresponding networks without diagonal connections are 1.

Spangle

Work-Optimal thinning algorithm on SIMD machines, object, using a pyramidal decomposition of the picture. With the Exclusive Read Exclusive Write (EREW) Parallel Random Access Machine (PRAM), our algorithm runs in .(log .) time using ../log .) processors. Same complexity is obtained using an SIMD hypercube. Both the PRAM and the Hypercube algorith

hieroglyphic

花费

Constant-time convexity problems on reconfigurable meshes, algorithms for a number of important computational geometry tasks relevant to image processing, computer graphics, and computer vision. In all our algorithms we assume that one or two .-vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size .. In this co