Thumbnail
Access Restriction
Open

Author Ezekiel, Jonathan ♦ Lüttgen, Gerald
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Symbolic Algorithm ♦ System Model ♦ Direct Measurement ♦ State-space Exploration Algorithm ♦ Pdmc Community ♦ Shared-memory Architecture ♦ Hard Way ♦ Painful Period ♦ Asynchronous System Model ♦ Parallelisation Overhead ♦ Parallel State-space Exploration Algorithm ♦ Several Challenge
Description We argue in this paper that benchmarking should be complemented by direct measurement of parallelisation overheads when evaluating parallel state-space exploration algorithms. This poses several challenges that so far have not been addressed in the literature: what exactly are those overheads, how can and cannot they be measured, and how should system models be selected in order to expose the causes of parallelisation (in)efficiencies? We discuss and answer these questions based on our experience with parallelising Saturation – a symbolic algorithm for generating state-spaces of asynchronous system models – on a shared-memory architecture. Doing so will hopefully spare newcomers to the growing PDMC community from having to learn these lessons the hard way, as we did over a painful period of almost three years.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Institution In PDMC, ENTCS (To Appear