Accession Number : ADA315774

Title :   Balancing Contention and Synchronization on the Intel Paragon.

Descriptive Note : Contractor's rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Bokhari, Shahid H. ; Nicol, David M.

PDF Url : ADA315774

Report Date : AUG 1996

Pagination or Media Count : 23

Abstract : The Intel Paragon is a mesh-connected distributed memory parallel computer. It uses an oblivious and deterministic message routing algorithm: this permits us to develop highly optimized schedules for frequently needed communication patterns. The complete exchange is one such pattern. Several approaches are available for carrying it out on the mesh. We study an algorithm developed by Scott. This algorithm assumes that a communication link can carry one message at a time and that a node can only transmit one message at a time. It requires global synchronization to enforce a schedule of transmissions. Unfortunately global synchronization has substantial overhead on the Paragon. At the same time the powerful interconnection mechanism of this machine permits 2 or 3 messages to share a communication link with minor overhead. It can also overlap multiple message transmission from the same node to some extent. We develop a generalization of Scott's algorithm that executes complete exchange with a prescribed contention. Schedules that incur greater contention require fewer synchronization steps. This permits us to tradeoff contention against synchronization overhead. We describe the performance of this algorithm and compare it with Scott's original algorithm as well as with a naive algorithm that does not take interconnection structure into account. The Bounded contention algorithm is always better than Scott's algorithm and outperforms the naive algorithm for all but the smallest message sizes. The naive algorithm fails to work on meshes larger than 12 x 12. These results show that due consideration of processor interconnect and machine performance parameters is necessary to obtain peak performance from the Paragon and its successor mesh machines.

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSORS, *MESH, *SYNCHRONIZATION(ELECTRONICS), *ROUTING, *DATA LINKS, *MESSAGE PROCESSING, PEAK VALUES, GLOBAL, INFORMATION EXCHANGE, DISTRIBUTED DATA PROCESSING, COMMUNICATIONS TRAFFIC, SIZES(DIMENSIONS), NODES, TRANSMITTANCE, BALANCE, CIRCUIT INTERCONNECTIONS, PATTERNS, OVERLAP, TRADE OFF ANALYSIS.

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE