Matching architecture to application via configurable processors: A case study with Boolean satisfiability problem

Ying Zhao, Sharad Malik, Albert Wang, Matthew W. Moskewicz, Conor F. Madigan

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

Boolean Satisfiability (SAT) is a classical NP-complete problem with both theoretical and practical interests. This paper presents our work in developing an application-specific processor for SAT based on a commercial configurable processor core. We customize the processor configuration and design new instruction extensions based on the data structure and atomic operations used in SAT. The customized processor has achieved around 2-4X speedup at a very low hardware cost. The small size of the processor makes it possible to integrate multiple processors and other customized logic into a single chip for an application-specific multiprocessor solution for SAT. Our work shows the strength of application-specific processing in accelerating applications with complex control and dynamic data structures - an area that has traditionally not been targeted by application-specific processing. It also demonstrates that configurable processor cores can be used to cut the development time and cost for designing and building such application-specific processors.

Original languageEnglish (US)
Article number65
Pages (from-to)447-452
Number of pages6
JournalProceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
DOIs
StatePublished - Jan 1 2001

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Matching architecture to application via configurable processors: A case study with Boolean satisfiability problem'. Together they form a unique fingerprint.

Cite this