[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 2, pp. 243-269 (May 2000)

Design Issues for Optimistic Distributed Discrete
Event Simulation

Yi-Bing Lin
Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
E-mail: liny@csie.nctu.edu.tw

A new class of interconnection networks called the hexcube is proposed. The hexcube is similar to the base-6 generalized hypercube in structure but has a simpler interconnection scheme. The present work shows that the hexcube is vertex symmetric and possesses topological properties similar to those of the hypercube. This implies that the costs of building parallel computers using the hexcube and using the binary hypercube are similar, and are much lower than those incurred using the based-6 generalized hypercube. A one-port broadcasting algorithm for the hexcube is proposed. New results for embeddings using the hexcube as the host topology are also presented. First, a reflected Gray code-like method for finding Hamiltonian cycles is developed. Second, algorithms for all two-dimensional mesh embedding with unit expansion and a dilation of no more than two are developed. Third, it is shown that a relatively large binary hypercube can be embedded into a hexcube with a dilation of no more than three and with almost optimal expansion.

Keywords: discrete event simulation, distributed systems, fault tolerance, memory management, time warp

Full Text () Retrieve PDF document (200003_05.pdf : 3,563,874 bytes)

Received July 27, 1998; accepted November 29, 1999.
Communicated by Chyi-Nan Chen.