Modelling and simulation of interconnection networks: A conservative parallel approach

Abstract

The use of conservative parallel simulation techniques to accelerate multistage interconnection network simulation is addressed. The conventional null-message approach to resolving the deadlock problem in conservative simulation may lead to a livelock if lookahead cannot be guaranteed. We propose a new deadlock/livelock free scheme using null messages, but without the presumed lookahead, to co-ordinate the parallel simulation. A flushing mechanism to address the combinatorial explosion of memory consumption due to such null messages is also discussed. Our analysis shows that the proposed flushing mechanism effectively reduces the memory consumption from exponential to linear. Different partitioning and transformation techniques are used to map the simulation program onto multiprocessor platforms. Both the empirical and analytical results show an exceptional phenomenon that a balanced simulation workload distribution may not necessarily translate into better run-time performance.