loading...
Delay-Insensitive Synchronization on a Message-Passing Architecture with an Open Collector Bus
PORTUGAL January 24-January 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/EMPDP.1996.5005714th Euromicro Workshop on Parallel an ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
H. Bekker, Dept. of Comput. Sci., Groningen Univ., Netherlands
E.J. Dijkstra, Dept. of Comput. Sci., Groningen Univ., Netherlands
Abstract: The performance of some algorithms, running on a message passing computer, is limited by the high latency of global communications. To increase the performance, a simple open collector bus operated by delay insensitive programs running on each processor can be used. We illustrate this by an example: the constraint algorithm SHAKE as used in Constraint Molecular Dynamics simulation. We present a parallelizable SHAKE algorithm and show how it can be implemented on a ring architecture. On a large ring the use of message passing to synchronize SHAKE iterations may take up to 40% of the total time. We show how the communication time can be reduced by adding a very simple open collector bus, operated by a delay insensitive algorithm. In this way the time spent on the synchronization of SHAKE iterations will be negligible. We want to emphasize that this kind of open collector bus can be used with many delay insensitive algorithms. To show this we mention other possible applications.
Index Terms:
synchronisation; message passing; parallel architectures; multiprocessor interconnection networks; parallel algorithms; performance evaluation; physics computing; digital simulation; system buses; delay-insensitive synchronization; message passing architecture; open collector bus; performance; parallel algorithms; high latency; constraint algorithm; SHAKE; Constraint Molecular Dynamics simulation; ring architecture; communication time; delay insensitive algorithm; multiprocessor interconnection networks
Citation:
H. Bekker, E.J. Dijkstra, "Delay-Insensitive Synchronization on a Message-Passing Architecture with an Open Collector Bus," pdp, pp.0075, 4th Euromicro Workshop on Parallel and Distributed Processing (PDP '96), 1996
Usage of this product signifies your acceptance of the Terms of Use.