Bandwidth and Wavefront Reduction for Static Variable Ordering in Symbolic Model Checking

    Research output: Working paper

    7 Downloads (Pure)

    Abstract

    We demonstrate the applicability of bandwidth and wavefront reduction algorithms to static variable ordering. In symbolic model checking event locality plays a major role in time and memory usage. For example, in Petri nets event locality can be captured by dependency matrices, where nonzero entries indicate whether a transition modifies a place. The quality of event locality has been expressed as a metric called (weighted) event span. The bandwidth of a matrix is a metric indicating the distance of nonzero elements to the diagonal. Wavefront is a metric indicating the degree of nonzeros on one end of the diagonal of the matrix. Bandwidth and wavefront are well studied metrics used in sparse matrix solvers. In this work we prove that span is limited by twice the bandwidth of a matrix. This observation makes bandwidth reduction algorithms useful for obtaining good variable orders. One major issue we address is that the reduction algorithms can only be applied on symmetric matrices, while the dependency matrices are asymmetric. We show that the Sloan algorithm executed on the total graph of the adjacency graph gives the best variable orders. Practically, we demonstrate that our work allows to call standard sparse matrix operations in Boost and ViennaCL, computing very good static variable orders in milliseconds. Future work is promising, because a whole new spectrum of more off-the-shelf algorithms, including metaheuristic ones, become available for variable ordering.
    Original languageEnglish
    PublisherarXiv.org
    Number of pages17
    Publication statusPublished - 27 Nov 2015

    Keywords

    • Sparse matrix
    • Wavefront
    • Event locality
    • Petri net
    • METIS-316833
    • Profile
    • EWI-26751
    • IR-99727
    • Symbolic model checking
    • Event span
    • Bandwidth
    • Decision diagram

    Fingerprint Dive into the research topics of 'Bandwidth and Wavefront Reduction for Static Variable Ordering in Symbolic Model Checking'. Together they form a unique fingerprint.

  • Cite this