The first IEEE Programming Challenge of the International Workshop on Logic and Synthesis (IWLS) was launched in December 2005. IEEE CEDA sponsored together with Synplicity and Cadence Design Systems the first programming challenge of the International Workshop on Logic and Synthesis (IWLS). With the help of these funds six participating students received a travel grant and could travel to the IWLS workshop held June 2006 in Vail, Colorado. In addition to the travel grants the committee of the programming challenge awarded two entries of the challenge with a Best Contribution Award. Each of the two awards came with a cash prize of $250.

The programming challenge was organized and co-chaired by Florian Krohm (IBM) and Christoph Albrecht (Cadence Berkeley Labs). A committee consisting of Robert Brayton (UC Berkeley), Valavan Manohararajah (Altera) and the two co-chairs judged the entries by how good the implementations make use of the OpenAccess database and the OA Gear infrastructure, how well the functionality is architected to allow maximum versatility, how the algorithms scale for large circuits, how good the unit and regression tests and the documentation are, and how well the OA Gear coding standard is followed.

The students Kai-hui Chang and David A. Papa from the University of Michigan received the Best Contribution Award for their contribution Simulation and Equivalence Checking. They developed a logic simulation engine which is 100 times faster than the simulator released previously with the OA Gear package. They use their simulator in combination with MiniSAT for combinational equivalence checking, and developed a new metric of circuit similarity that can be used in incremental verification and debugging. Kai-hui and David also integrated their simulator and equivalence checker into the OA Gear GUI Bazaar.

More information: Technical abstract, Presentation at the 9th OpenAccess+ Conference (10 Nov 2006).

Qi Zhu and Nathan Kitchen from the University of California at Berkeley received the Best Contribution Award for their submission entitled SAT sweeping with Local Observability Dont Cares. They implemented a SAT sweeping algorithm which has applications in Boolean reasoning and functional verification. SAT sweeping finds nodes which are equivalent by simulating random vectors and then proving the equivalence by solving a SAT instance. The circuit is simplified by merging equivalent nodes. Qi and Nathan extended this technique by merging nodes which are not functionally equivalent but whose functional difference is not observable within paths of bounded length. Their implementation makes extensive use of the OA Gear and-inverter graph.

More Information: Technical abstract, detailed paper at DAC06, audio recording of DAC06 presentation.

Both prize-winning submissions are now part of the OA Gear release.

The first IWLS Programming Challenge winners with the event organizers. Left to right on the back row: Robert Brayton, Valavan Manohararajah, David A. Papa, Kai-hui Chang, Florian Krohm, Petra Faerm, Donal Chai. Front row: Qi Zhu, Nathan Kitchen, and Christoph Albrecht.