TY - JOUR
T1 - Matching architecture to application via configurable processors
T2 - A case study with Boolean satisfiability problem
AU - Zhao, Ying
AU - Malik, Sharad
AU - Wang, Albert
AU - Moskewicz, Matthew W.
AU - Madigan, Conor F.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0035188355&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035188355&partnerID=8YFLogxK
U2 - 10.1109/ICCD.2001.955064
DO - 10.1109/ICCD.2001.955064
M3 - Article
AN - SCOPUS:0035188355
SN - 1063-6404
SP - 447
EP - 452
JO - Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
JF - Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
M1 - 65
ER -