Author: National University of Singapore. Dept. of Information Systems and Computer Science

Publisher:

Published: 1994

Total Pages: 24

ISBN-13:

Abstract: "Multistage interconnection networks are used in a number of application areas such as parallel computers and high-speed communication systems. As the performance of these systems lies on an efficient design of the interconnection network, a thorough analysis of the network's performance is important. Mathematical analysis so far provides inadequate results and simulation analysis using a uniprocessor usually requires long hours to evaluate large networks. In this paper, parallel simulation technique is used to speedup the execution. The conventional null-message approach to resolving deadlock problem in conservative simulation is based on a lookahead mechanism. For some application domains, unfortunately, the lookahead information is not available. Consequently, parallel simulation using null messages can result in livelock. We propose a deadlock/livelock free scheme using null messages, but without the guaranteed lookahead, to coordinate the simulation. In addition, we investigate different partitioning and transformation techniques for mapping a simulation program onto multicomputers. A flushing mechanism to address the combinatoric explosion of using null- message in conservative simulation is also discussed. Our analysis shows that the proposed flushing mechanism effectively reduces the number of null messages from exponential to linear."