Paper Details

@InProceedings{MorseWelch90,
  title = "{D}iffusion limited aggregation: {A}n example of real-time parallelisation",
  author= "Morse, D. R. and Welch, A. M. and Welch, Peter H.",
  editor= "Zedan, Hussein S. M.",
  pages = "248--261",
  booktitle= "{OUG}-13: {R}eal-{T}ime {S}ystems with {T}ransputers",
  isbn= "90 5199 041 3",
  year= "1990",
  month= "sep",
  abstract= "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."
}

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.