5. The Compilation Problem

This chapter presents in detail the compilation task, which, given the biochemical application and biochip architecture models as inputs, produces the electrode actuation sequence required to run the application on the given biochip. Each of the compilation subtasks, such as, allocation, binding, placement, scheduling and routing are discussed in a corresponding subsection. These subtasks have a high computational complexity, and we have used a heuristic algorithm called “List Scheduling” as a starting point for providing solutions to them. Hence, this chapter also covers the “List Scheduling” heuristic. The compilation task also takes as input a “library of modules” on which the operations on the biochemical applications have to execute. We present a method to determine a library of “circular-route modules”, which will be used in Part IV of the book, to support application-specific architectures. To simplify the presentation, this chapter presents the compilation task assuming that an operation executes on a static rectangular “module”. However, as discussed in Chap. 3, we also consider other operation execution models in the book; these will be covered in the next chapters related to the compilation task.