State-space-partitioning-based approaches have been proposed in the literature to address the state-explosion problem in model checking. These approaches, whether sequential or distributed, perform a large amount of work in the form of interpartition (crossover) image computations, which can be expensive. A model-checking algorithm that aggregates these expensive crossover images by localizing computation to individual partitions is presented. It reduces the number of crossover images and drastically outperforms extant approaches in terms of crossover image computation cost as well as total model-checking time, often by two orders of magnitude.

Formal verification, especially error detection, is rapidly increasing in importance with the rising complexity of designs. The main constraint in verification is the total amount of resources available - both time as well as memory. Most attempts at verification only use a single processor. Recently, various attempts have been made to use parallel and distributed methods for verification. However, verification in a Grid-based environment has not yet been very widely adopted. As personal computers gain in computing capacity, the concept of computation grids is gaining acceptance. Here, a grid is a network of machines that may not be dedicated to a specific computational use, but may only be available some of the time. This is a unique environment where massive parallelism is possible by using otherwise idle CPU cycles from a large number of computers. Such processors may even be in geographically diverse locations. We describe a Grid-based verifi- cation environment for detecting errors in a design. We verify user-written assertions as well as properties, e.g. unreachable code, index-out-of-range, that are extracted automatically from the design using a state-of-the-art HDL parser. Such an approach can help the user to quickly find RTL level bugs earlier in the design cycle.

Partitioned BDD-based algorithms have been proposed in the literature to solve the memory explosion problem in BDD-based verification. Such algorithms can be at times ineffective as they suffer from the problem of scheduling the relative order in which the partitions are processed. In this paper we present a novel multi-threaded reachability algorithm that avoids this scheduling problem while increasing the latent parallelism in partitioned state space traversal. We show that in most cases our method is significantly faster than both the standard reachability algorithm as well as the existing partitioned approaches. The gains are further magnified when our threaded implementation is evaluated in the context of a parallel framework.