UCR



Philip Brisk: CS.179J Design Project in Embedded Systems


Shanghai Aquarium                             Shanghai Aquarium

CS.179J Design Project in Computer Architecture and Embedded Systems

Winter 2012, Basic Information

Discussion:  Mon.      11:10 am -12:00 pm     MSE 113
Lab:               Tues.     6:10 pm - 9:00 pm         WCH (formerly ENGR2) 136 

Instructor:         Philip Brisk (first_name@cs.ucr.edu)
Office Hours:   Open Door Policy, M-Th., 10:00am - 3:00pm              WCH (formerly ENGR2) 339 (or 464)            

Teaching Assistant:    Ben Sanders
Office Hours:    Tues.    1:00 pm - 3:00 pm     WCH (formerly ENGR2) 225 

Final Exam:        None 

The course will use iLearn extensively!

Course Catalog Information

Catalog Entry:     CS 179J Computer Architecture and Embedded Systems (4 units)
Discussion:        1 hour
Laboratory:         9 hours
Prerequisites:    CS 100, CS 111, CS 122A, CS 161 with grades of C- or better or consent of instructor. ENGR 180W
                              Additional upper division units in Computer Science. 

Covers the planning, design, implementation, testing, and documentation of a computer architecture and embedded systems-related system. Incorporates using techniques presented in previous related courses. Emphasizes professional and ethical responsibilities; the need to stay current on technology; and its global impact on economics, society, and the environment.

Course Requirements and Grading

Students are expected to work in groups ranging from 2-4 students, depending on the scope of the project. Remember, you only have 10 weeks (plus the final exam week)! 

5%:     First project demonstration and report (approx. Week 3-4)
5%:     Second project demonstration and report (approx. Week 6-7)
25%:   Final project demonstration (approx. Week 10 or Finals)
10%:   Final project presentation (PowerPoint)
50%:   Final project report
5%:     Archive and blog (explained later in the syllabus) 

Attendance in the discussion section on Mondays is mandatory. 
Attendance in the laboratory section is optional, depending on the needs of the group.

Course Project Theme: Programmable Microfluidics

The theme of this CS.179J offering is "Programmable Microfluidics," which is an emerging area of interdisciplinary research that will miniaturize and automate chemistry and biochemistry in the coming years. The first week of lecture will provide an overview of different programmable microfluidic technologies and platforms.

Each group is free to choose one (or more) microfluidic technologies and platforms to target. The group will design a software simulator for the target technology, and then develop a compilation flow targeting their simulator. Benchmark applications will be provided.The first week of course will be reading-intensive, as students will be exposed to a variety of different microfluidic technologies and architectures, so that each group can make an informed choice of platform. The second week will teach algorithmic optimization strategies that may be useful. The remaining weeks of the course will introduce new key algorithmic steps that need to be solved during the compilation flow. Groups are free to implement any algorithm that they want, as long as it works. Most problems involved with compilation are NP-complete, so there is an expected tradeoff between algorithmic runtime and the quality of solution that is produced.

In the future, microfluidic devices are likely to be controlled by small embedded processors, rather than expensive desktop or laptop PCs. An important component of this class is to evaluate the compilation flow that is developed using both a desktop or laptop PC (or CS department server), and an embedded processor, which has severe resource constraints. (see the available equipment below).

If groups are so-inclined, FPGA-driven control is also a possibility. This would allow the real-time execution of more computationally powerful algorithms than would be possible using an embedded processor, or even a desktop or laptop PC. This option is recommended only for students with strong hardware design experience (e.g., you have passed CS.161/161L and CS.122A with very good grades).

●  The first demo will verify a correctly functioning simulator for the chosen microfluidic technology and architecture.
●  The second demo will show the initial steps of a compilation flow targeting microfluidic technologies; at least one step should be complete.
●  The final demonstration at the end of the quarter will establish a complete compilation flow from the specification of a chemical protocol through correct execution on the simulator.

Required Textbooks

Break Away with Intel Atom Processors    
A Guide to Architecture Migration
Lori Matassa and Max Domeika
Intel Press (2010)

Introduction to Embedded Systems
A Cyber Physical Systems Approach
Edward A. Lee and Sanjit A. Seshia
http://LeeSeshia.org (2011)

+ weekly reading assignments, typically papers published by the IEEE, ACM, or AAAS.

Optional Textbooks

Microelectrofluidic Systems
Modeling and Simulation
Tianghao Zhang, Krishnendu Chakrabary, and Richard B. Fair
CRC Press (2002)

Digital Microfluidic Biochips
Synthesis, Testing, and Reconfiguration Techniques
Fei Su and Krishnendu Chakrabarty
CRC Press (2006)

Digital Microfluidic Biochips
Design Automation and Optimization
Tao Xu and Krishnendu Chakrabarty
CRC Press (2010)

Synthesis and Optimization of Digital Circuits
Giovanni De Micheli
McGraw-Hill (1994)

Equipment

Intel has generously provided UCR with a generous equipment donation and financial support under the condition that the equipment be used in this offering of CS 179J:

●  Ten Inforce Atom Processor Development Boards pre-loaded with TimeSys Linux (a variant of Fedora). These development boards are fully functional  computers. To use them, you simply need to plug in a monitor to the VGA port, and a keyboard and mouse into two of the four USB slots. The boards also have an Ethernet connection for networking applications, and 320 GB Western Digital hard drives.  

●  One “Stellarton” development board. Stellarton is an Intel Atom processor with Altera Arria FPGA in the same package. The development board includes on-board DRAM, an Ethernet and I/O card, Nvidia GPU, and an 80 GB Western Digital Hard Drive. 

My intention is to provide 7 or 8 Atom Boards to groups for project use, reserving the rest as backups in case some of the boards are lost, stolen, or break. The Stellarton board will sit in my laboratory; only one group will be able to use the Stellarton board to avoid conflicts. I intend to provide laboratory access to all students who will use the Stellarton board.

Other Available Equipment (not provided by Intel): 

●  One or two Xilinx Virtex-6 EK-V6-ML605-G development boards. (Fairly high-end, large capacity FPGAs, but one generation behind the state-of-the-art Virtex 7’s) 

●  Several Xilinx Spartan development boards (e.g., those used in CS 122A in Fall Quarter). 

●   A variety of Microcontrollers for embedded systems-oriented projects. 

●   The RIBS / RIMS toolset used in CS 120B. Feel free to use these tools to generate state machines for your projects, if you think they will be helpful.

Links to Intel Embedded Resources

Atom Tunnel Creek Notes (University of Colorado at Boulder)
Tunnel Creek Board Development Information (Inforce Computing)
Tunnel Creek User Guides (Inforce Computing)
Intel/Cornell Embedded Computing Competition

General Project Information

●     UCR dictates roughly 3-4 hrs/week per unit. 4 units = 12-16 hrs per week. Expect to spend time on this capstone senior project. The project work begins right away. 

●     Each group will do an individual project      

●     The best group projects are often set up where each student in the group works on an individual project; all of the projects can be collectively assembled to form a larger fully functional system toward the end of the quarter.      

●     Group work is a requirement for the course. Depending on the nature of the project, the interaction within the group may be tightly or loosely coupled.      

●     All students are expected to participate in the design, implementation, and documentation of the project. As examples, the following divisions of labor are absolutely unacceptable!        

             ●  one student wrote code, the other debugged the code         
             ●  one student did the implementation work; the other the documentation 

●     Appropriate assistance of team members (as well as other classmates) is allowed, including providing advice/tips, helping debug, testing another student's design, and     cooperatively learning to use new parts/tools.  

●     All code in a group’s project must be written by members of that group. Any code used that is not written by the student must be approved by the instructor or TA and clearly cited in the code. 

●     Students may choose from predefined projects or define their own similar project with teacher approval.  

●     Students will submit successively more complete project versions during the quarter. Each version must function (within reason). Monolithic projects that produce no observable output until the very end of the course period are discouraged.  

●     Each version will include documentation, presentation, test information, engineering logs, source code/schematics, demonstration, and report. The final report must include all intermediate reports as distinct chapters to demonstrate progression of the project throughout the quarter. 

●     The final version of the project includes an oral presentation using PowerPoint (or equivalent) slides. All students in each project team are required to participate.      

●     Students have different levels of comfort with public speaking; students will not be graded on this factor. That being said, professional well-rehearsed presentations with high quality meaningful slides are expected. The talk should last plus or minus 1 minute of the allotted time. 

●     Under most circumstances, all students in a group will receive the same grade for the project; however, the instructor reserves the right to give different grades to students in the same group if he feels that it is warranted.

Academic Integrity

Important note: If any member of your group commits an act of academic dishonesty, all members of the group will receive a failing grade! It is your responsibility to know UCRs policy on academic dishonesty.

Student Expectations

Although it is your responsibility to know the details of the above, the instructor explicitly states here that using a single sentence from another source, without acknowledging that source, is plagiarism and will get you a failing grade. 

You are responsible for any announcements or changes the instructor makes in classes, even if you are not there; most announcements or changes will be made on iLearn.  

The instructor does not like to be distracted by cell phones ringing in class. If your cell phone or beeper goes off in class you will be fined one letter grade (first offense), or give you an F (second offense). You should also turn off your cell phone before visiting the instructor’s in his office. (Note: The instructor wilI make an exception to the above rules if you explain in advance why this stance creates a hardship for you).

Project Report Requirements

Download here.

Archiving Your Work

Your group must choose a member to act as an archivist.  

Every Sunday night (or early Monday morning), the archivist must create a zip file that contains all files (including source code, notes, documentation and emails between group members) your group has created in the last week.  The file name should be a concatenation of the group members last names (in alphabetical order), separated by underscores and followed by the week number. For example:   

Jones_Smith_Zoe_Week7.zip 

The instructor or TA will create a submission option on iLearn for each group’s archive each week. Submission of a weekly archive is a requirements. The instructor or TA reserves the right to inspect the archives at any time during the quarter.   All of the archives must be copied onto the CD-ROMS at the end of the quarter as well. In addition, the CD-ROMS should contain your group’s final working project, together with a readme.txt file that clearly explains how to get it up and running. 

Blog

Each group must maintain a blog on iLearn that contains a “log” of your progress. The blog must be updated at least once per week with an informal record of the group’s progress. An example of the expected level of detail is: 

Jan-12-03: After the meeting today: Joe agreed to track down the “spatial databases” book, and the two papers Dr. Keogh recommend. Sue is going to see if MS Access will support the XTC language. Mike will do a web search to find resources on SAMS. 

Jan-13-03: Mike briefed the group on the BBC tree, which may be better than the R-tree for our project. Sue noted that XTC has a file size limit of 12k, which means that we cannot use it for our project.

 

Course Schedule

UC Riverside is based on a 10 week quarter system (+1 week of finals). This course has been designed for a 10 week implementation. Instructors who teach a 14-16 week semester are encouraged to contact Dr. Brisk for suggestions regarding additional course material that goes beyond what is scheduled here.

Students are expected to read all of the papers listed here, in order to participate in an informed discussion in the class. As this is a senior design project, there will be no quizzes or exams; however, students must establish active participation in the course, in addition to simply doing their projects.

 
Week 1: Microfluidic Technology Overview

Objective: Expose students to a variety of microfluidic technologies, architectures, and programming languages. Allow the students to explore these materials and choose appropriate technologies, architectures, and languages for use in their projects.

Survey Papers

George M. Whitesides: The origins and future of microfluidics. Nature, 442(27): 268-273 (2006)

R. B. Fair: Digital microfluidics: Is a true lab-on-a-chip possible?, Microfluidics and Nanofluidics 3: 245-281 (2007)

Krishnendu Chakrabarty: Design Automation and Test Solutions for Digital Microfluidic Biochips. IEEE Trans. on Circuits and Systems 57-I(1): 4-17 (2010) 

Krishnendu Chakrabarty, Richard B. Fair, Jun Zeng: Design Tools for Digital Microfluidic Biochips: Toward Functional Diversification and More Than Moore. IEEE Trans. on CAD of Integrated Circuits and Systems 29(7): 1001-1017 (2010) 

Tsung-Yi Ho, Krishnendu Chakrabarty, Paul Pop: Digital microfluidic biochips: recent research and emerging challenges. CODES+ISSS 2011: 335-344

Microfluidic Technologies

M.G. Pollack, A.D. Shenderov, R.B. Fair: Electrowetting-based actuation of droplets for integrated microfluidics, Lab on a Chip, 2: 96-101 (2002)

Phil Paik , Vamsee K. Pamula , Michael G. Pollack and Richard B. Fair: Electrowetting-based droplet mixers for microfluidic systems, Lab on a Chip 3:28-33 (2003)

William H. Grover, Alison M. Skelley, Chung N. Liu, Eric T. Lagally, Richard A. Matthies: Monolithic membrane valves and diaphragm pumps for practical large-scale integration into glass microfluidic devices. Sensors and Actuators B 89: 315-323 (2003)

Jessica Melin and Stephen R. Quake: Microfluidic large-scale integration: the evolution of design rules for biological automation. Ann. Rev. Biophys. Biomol. Struc. 36: 213-231 (2007)

Microfluidic Architectures

John Paul Urbanski, William Thies, Christopher Rhodes, Saman Amarasinghe, and Todd Thorsen: Digital Microfluidics Using Soft Lithography, Lab on a Chip 6: 96-104 (2006)

Ahmed M. Amin, Mithuna Thottethodi, T. N. Vijaykumar, Steven Wereley, Stephen C. Jacobson: Aquacore: a programmable architecture for microfluidics. ISCA 2007: 254-265

Erik C. Jensen, Bharath, P. Bhat, and Richard A. Mathies: A digital microfluidic platform for the automation of quantitative biomolecular assays. Lab on a Chip 10: 685-691 (2010)

Luis M. Fidalgo and Sebastian J. Maerkl: A software-programmable microfluidic device for automated biology. Lab on a Chip 11: 1612-1619 (2011)

Joo Hyon Noh, Jiyong Noh, Eric Kreit, Jason Heikenfeld, and Philip D. Rack: Toward active-matrix lab-on-a-chip programmable electrofluidic control enabled by arrayed oxide thin film transistors. Lab on a Chip 12: 353-360 (2012)

Biochemical Programming Languages

W. Thies, J. P. Urbanski, T. Thorsen, and S. Amarasinghe: Abstraction layer for scalable microfluidic biocomputers. Natural Computing 7(2): 255-275 (2008)

Larisa N. Soldatova, Wayne Aubrey, Ross D. King, and Amanda Clare: The EXACT description of biomedical protocols. Bioinformatics 24(13): i295-i303 (2008)

Vaishnavi Ananthanarayanan and William Thies: Biocoder: a programming language for standardizing and automating biology protocols. Journal of Biological Engineering 4(13) (2010).

Benchmark Assays

Fei Su and Krishnendu Chakrabarty: Benchmarks” for Digital Microfluidic Biochip Design and Synthesis. Duke University, 2006. Available for download here.

 
Week 2: Algorithmic Optimization Strategies

Objective: Most of the interesting problems in microfluidic compilation are NP-complete. Many papers that have been published employ complicated optimization techniques in order to find high quality solutions, including simulated annealing, genetic algorithms, and integer linear programming (ILP), among others. These strategies are computationally intensive, and are therefore poor choices for embedded processors; however, it is still important to learn about them so that students can read and understand the papers that describe them.

Simulated Annealing

D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Schevon: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning. Operations Research, 37(6): 865-892 (1989) 

D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Schevon: Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning.  Operations Research 39(3): 378-406 (1991).

Genetic Algorithms

James C. Bean: Genetic Algorithms and Random Keys for Sequencing and Optimization. INFORMS Journal on Computing 6(2): 154-160 (1994)

Samir W. Mahfoud, David E. Goldberg: Parallel Recombinative Simulated Annealing: A Genetic Algorithm. Parallel Computing 21(1): 1-28 (1995)

Integer Linear Programming

J. Cole Smith and Z. Caner Taskin: A tutorial guide to mixed-integer programming. University of Florida, March 26, 2007.

 

Week 3: Scheduling

Objective: The first stage of microfluidic compilation is to schedule the assay. Many different algorithms have been proposed in the literature, ranging from efficient greedy heuristics that produce relatively poor quality solutions, to optimal algorithms that run in worst-case exponential time (assuming that P≠NP). This week reviews the best known scheduling algorithms.

Papers

Jie Ding, Krishnendu Chakrabarty, Richard B. Fair: Scheduling of microfluidic operations for reconfigurabletwo-dimensional electrowetting arrays. IEEE Trans. on CAD of Integrated Circuits and Systems 20(12): 1463-1468 (2001) 

Andrew J. Ricketts, Kevin M. Irick, Narayanan Vijaykrishnan, Mary Jane Irwin: Priority scheduling in digital microfluidics-based biochips. DATE 2006: 329-334 

Fei Su, Krishnendu Chakrabarty: High-level synthesis of digital microfluidic biochips. JETC 3(4): (2008)

Lingzhi Luo, Srinivas Akella: Optimal Scheduling of Biochemical Analyses on Digital Microfluidic Systems. IEEE T. Automation Science and Engineering 8(1): 216-227 (2011)

 

Week 4: Placement

Objective: Once a schedule has been computed, assay operations need to be placed in space (i.e., on the microfluidic device) and in time (i.e., at the correct moments according to the schedule). This week reviews the best known placement algorithms.

Papers

Fei Su, Krishnendu Chakrabarty: Module placement for fault-tolerant microfluidics-based biochips. ACM Trans. Design Autom. Electr. Syst. 11(3): 682-710 (2006) 

Ping-Hung Yuh, Chia-Lin Yang, Yao-Wen Chang: Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation. JETC 3(3): (2007) 

Chen Liao, Shiyan Hu: Multiscale variation-aware techniques for high-performance digital microfluidic lab-on-a-chip placement. IEEE Trans. Nanobioscience 10(1): 51-58 (2011)

 

Week 5: Droplet Routing I

Objective: Once assay operations have been scheduled and placed in time and space, it is necessary to transport fluid to the appropriate module locations; in practice, this can be done in real time. This is a challenging problem that shares some principle similarities with path planning in robotics. This week introduces the first batch of droplet routing papers, which are relatively simple (compared to the algorithms introduced in Week 6)

Papers

Eric J. Griffith, Srinivas Akella: Coordinating Multiple Droplets in Planar Array Digital Microfluidic Systems. I. J. Robotic Res. 24(11): 933-949 (2005) 

Fei Su, William L. Hwang, Krishnendu Chakrabarty: Droplet routing in the synthesis of digital microfluidic biochips. DATE 2006: 323-328 

Karl-Friedrich Böhringer: Modeling and Controlling Parallel Tasks in Droplet-Based Microfluidic Systems. IEEE Trans. on CAD of Integrated Circuits and Systems 25(2): 334-344 (2006) 

Pranab Roy, Hafizur Rahaman, Parthasarathi Dasgupta: A novel droplet routing algorithm for digital microfluidic biochips. ACM Great Lakes Symposium on VLSI 2010: 441-446 

Kamaelsh Singha, Tuhina Samanta, Hafizur Rahaman, Parthasarathi Dasgupta: Method of droplet routing in digital microfluidic biochip. IEEE/ASM International Conference on Mechatronics and Embedded Systems and Applications (MESA) 2010: 521-256 

 

Week 6: Droplet Routing II

Objective: Here, we introduce droplet routing algorithms that are more algorithmically complex than those discussed during Week 5.

Papers

Minsik Cho, David Z. Pan: A High-Performance Droplet Routing Algorithm for Digital Microfluidic Biochips. IEEE Trans. on CAD of Integrated Circuits and Systems 27(10): 1714-1724 (2008) 

Ping-Hung Yuh, Chia-Lin Yang, Yao-Wen Chang: BioRoute: A Network-Flow-Based Routing Algorithm for the Synthesis of Digital Microfluidic Biochips. IEEE Trans. on CAD of Integrated Circuits and Systems 27(11): 1928-1941 (2008) 

Tsung-Wei Huang, Tsung-Yi Ho: A fast routability- and performance-driven droplet routing algorithm for digital microfluidic biochips. ICCD 2009: 445-450

 

Week 7: Multi-Stage Compilation Algorithms

Objective: Scheduling, placement, and routing are all NP-complete problems. To achieve better overall global results, several solvers have been introduced in the past which solve two or three of these problems together, in conjunction with one another. For example, scheduling can become aware of the placement, or the placement can be optimized to enhance routability and yield shorter droplet routes. This week reviews the best-known multi-stage compilation algorithms.

Papers

Fei Su, Krishnendu Chakrabarty: Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips. DAC 2005: 825-830 

Tao Xu, Krishnendu Chakrabarty: Integrated droplet routing and defect tolerance in the synthesis of digital microfluidic biochips. JETC 4(3): (2008) 

Elena Maftei, Paul Pop, Jan Madsen: Tabu search-based synthesis of digital microfluidic biochips with dynamically reconfigurable non-rectangular devices. Design Autom. for Emb. Sys. 14(3): 287-307 (2010) 

Elena Maftei, Paul Pop, Jan Madsen: Routing-based synthesis of digital microfluidic biochips. CASES 2010: 41-50 

Pranab Roy, Hafizur Rahaman, Parthasarathi Dasgupta: Two-level cluster-based technique for intelligent droplet routing in digital microfluidic biochips. Integeration: The VLSI Journal (2012)

 
Week 8: Wash Droplet Routing

Objective: One problem that can occur when routing fluids is residue removal. As fluids travel through a chip, they can leave residue behind, which contaminates other fluids that cross the path of the original fluid. To eliminate contamination, it becomes necessary to wash portions of the chip periodically. This week reviews the best known algorithms for washing chips to eliminate cross-contamination.

Papers

Yang Zhao, Krishnendu Chakrabarty: Cross-contamination avoidance for droplet routing in digital microfluidic biochips. DATE 2009: 1290-1295

  Yang Zhao, Krishnendu Chakrabarty: Synchronization of washing operations with droplet routing for cross-contamination avoidance in digital microfluidic biochips. DAC 2010: 635-640 

Tsung-Wei Huang, Chun-Hsien Lin, Tsung-Yi Ho: A Contamination Aware Droplet Routing Algorithm for the Synthesis of Digital Microfluidic Biochips. IEEE Trans. on CAD of Integrated Circuits and Systems 29(11): 1682-1695 (2010) 

Debasis Mitra, Sarmishtha Ghoshal, Hafizur Rahaman, Krishnendu Chakrabarty, Bhargab B. Bhattacharya: Test Planning in Digital Microfluidic Biochips Using Efficient Eulerization Techniques. J. Electronic Testing 27(5): 657-671 (2011) 

 

Week 9: Fault Detection and Recovery

Objective: One problem that can occur when routing fluids is residue removal. As fluids travel through a chip, they can leave residue behind, which contaminates other fluids that cross the path of the original fluid. To eliminate contamination, it becomes necessary to wash portions of the chip periodically. This week reviews the best known algorithms for washing chips to eliminate cross-contamination.

Papers

  Yang Zhao, Tao Xu, Krishnendu Chakrabarty: Integrated control-path design and error recovery in the synthesis of digital microfluidic lab-on-chip. JETC 6(3): (2010) 

Mirela Alistar, Elena Maftei, Paul Pop, and Jan Madsen: Synthesis of biochemical applications on digital microfluidic biochips with operation variability. Symposium on Design, Test, Integration, and Packaging of MEMS/MOEMS (DTIP) 2010: 350-357 

Yan Luo, Krishnendu Chakrabarty, Tsung-Yi Ho: A cyberphysical synthesis approach for error recovery in digital microfluidic biochips. DATE 2012: 1239-1244

 

Week 10: Wrap Up

Objective: Prepare students for project demonstration, final  presentation, and project report; no new lecture material is presented.

 

Examples of Successful Projects

Posted WITH permission of all students involved.

Non-overlapping Graph Algorithms and Simulations
Brian Crites, Joe Dean, Ted Duong, Aditya Tammewar


More Information

General Campus Information

University of California, Riverside
900 University Ave.
Riverside, CA 92521
Tel: (951) 827-1012

Career OpportunitiesUCR Libraries
Campus StatusDirections to UCR

College Information

Bourns College of Engineering
Bourns Hall

Tel: (951) 827-5190
Fax: (951) 827-3188
E-mail: systems@cs.ucr.edu

Related Links

Footer