A cache-based parallel genetic algorithm for the BDD variable ordering problem - Costa, Umberto S.; Moreira, Anamaria M.; Déharbe, David (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 2000: Anais do XII Symposium on Computer Architecture and High Performance ComputingDO - 10.5753/sbac-pad.2000.41209, 2000)
Binary Decision Diagrams (BDDs) have proved to be a powerful representation for Boolean functions. Particulary, they are a very useful data structure for the symbolic model checking of a digital circuits and other finite state systems, as well as other problems. Nevertheless, the size of the BDD representation of these functions is highly dependent on the order of the function arguments, also called variables, and to find such good ordering is an NP-Complete problem. Many heuristics have been proposed to solve this problem, as our Parallel Genetic Algorithm presented in [4], where we got excellent results in terms of paralelization. Now, we present a new version of our algorithm, this time with a cache system, together with experimental results.