Diffusion limited aggregation: An example of real-time parallelisation
Authors: Morse, D. R., Welch, A. M., Welch, Peter H.
The simulation of the growth of Diffusion-Limited Aggregates (DLA) is representative of a class of 'shared' data-structure computations that does not yield to traditional parallelisation methods (such as 'farming', 'geometric decomposition' and 'data-flow'). The difficulty is that the shared data-structure is large and evolving, the required access to it from each processor is random and very high, and the computation per access is very low. These conditions also make these problems most unsuitable for shared-memory parallel computers.This paper presents a parallelisation technique that does give linear speed-up for this problem (at least, for up to 32 transputers). The cost-effectiveness of the solution compares favourably with those published that use vector-processing machines.The success of the parallelisation depends on real-time issues associated with keeping each worker transputer sufficiently up-to-date with all its colleagues. Some 'quasi-relativistic' effects need to be taken into account as well!The speed-ups achieved through this parallelisation are used to investigate the effect of various parameters (such as stride length and background drift) on the kind of DLA growth that is obtained. These studies would not be practical without the savings in time that have been realised from a parallel implementation of the DLA simulation.Finally, we characterise the features of those applications for which this parallelisation method is relevant.
OUG-13: Real-Time Systems with Transputers, Hussein S. M. Zedan, 1990, pp 248 - 261 published by IOS Press, Amsterdam
This record in other formats:Web page: BibTEX, Refer
Plain text: BibTEX, Refer
If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.
Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.
Pages © WoTUG, or the indicated author. All Rights Reserved.
Comments on these web pages should be addressed to: www at wotug.org