Parallelism in rule-based simulation

Exploiting parallelism at higher layers of architectures such as at application level and knowledge representation level is required to achieve higher speedups in Rule-based Simulation applications. In this thesis we investigate a parallel architecture which is based on a knowledge representation of the application. This high level architecture, the Semantic Network Architecture with Message Passing (SNAMP), uses a computer organization, structured on object-oriented and message-passing paradigms, which reduces the semantic-gap that exists between an application and its implementation. We have chosen a rule-based simulation application to demonstrate our concept. This rule-based simulation is a high level logic design simulation, which has tremendous data parallelism inherent in the application. Our methodology begins by translating the rule-based application onto a semantic network knowledge representation, then the resulting network is mapped onto a parallel computing system.;We modeled several examples of rule-based simulations with their functionality, using a simscript model. We measured close to linear speedups for these example applications. In addition to the simscript simulation model, we also developed application programs for the rule-based simulations on the Intel iPSC/2 hypercube. We measured almost linear speedups for these applications. For example, on a 16 node hypercube, the speedup measured is 13.6. It is also verified that the simscript model results are consistent with the measurements obtained on the hypercube. To overcome low bandwidth of iPSC/2 hypercube, we implemented message clustering to transmit message packets.;We investigated several partitioning to map the semantic networks onto the hypercube topology. We discovered that the simulated annealing approach results in lower cost partitions compared to the other methods studied in our research. However, this method requires large iterations to obtain a minimum cost partition. The thesis further proposes a massively parallel dedicated architecture for rule-based simulations and studied a possible VLSI implementation.