Getting Your Bits in Order

ENGINEERS FIND EDA software very time-consuming and must wait longer when working with larger chips. For tasks like microprocessor verification, huge server farms and dedicated hardware systems have been constructed. To better use server farms, EDA vendors are now developing new parallel algorithms. However, even with expensive computational resources, EDA software developers must make judicious choices of key algorithms and programming techniques. Some of these techniques are known only to exceptional engineers. A rule of thumb is that one exceptional software engineer is worth 20 mediocre ones. I was reminded of this rule when teaching an undergraduate course on algorithms and data structures at the University of Michigan. Students had to complete five software projects dealing with the implementation of standard data structures, maze routing, the construction of spanning trees, text processing, and the traveling salesman problem. With two trial submissions per day to an ‘‘autograder,’’ students received real-time feedback on the correctness and runtime of their programs, and also compared themselves to their peers. Year after year, the best student solutions in this course outperformed solutions prepared by teaching assistants, but this was not the case in the Fall 2009 semester. My assistant Mark was an undergraduate student who took this course in the previous semester, yet he could teach me a few things about algorithms. (He later represented Michigan at the ACM International Collegiate Programming Competition and won a gold medal at the world finals.) On Project 1, Mark’s program was several times faster than those submitted by students, but that was seemingly due to his optimized string I/O, as overall runtimes were small. On Project 2, the gap was even greater, although the best students in class tried hard to match Mark’s runtime, and I/O runtime was not important in this project because it was dwarfed by a branch-and-bound algorithm. Digging through Mark’s code, I identified the critical loop inside branch-and-bound. It began with for(; i; i1⁄4 i & i 1) {. . .. If you consider yourself an expert programmer, pause for a second and think what it does. In the meantime, let me tell you where you can learn such tricks and many more: in the book Hacker’s Delight by Henry S. Warren Jr. The book contains 16 chapters, starting with an introduction that defines an assembly-like instruction set to more concisely express bit-level algorithms (many chapters use C-like code instead of or in addition to those instructions). Bit-level algorithms are heavily used in high-performance data structures and are indispensable in many EDA contexts, including high-level and logic synthesis, formal and simulation-driven verification, detailed routing, and high-performance mask processing. I found that many chapters can be read out of order, and when background is required, the author provides references to the requisite earlier chapters. Chapter 2, ‘‘Basics,’’ discusses standard bitwise operations and their use to perform various tasks, such as compute max and min values without comparisons, rotate shifts, perform multibyte operations, and so on. Chapter 3 focuses on Book Reviews