Architecture Krish Presntation

Architectural-Level Synthesis of Digital Microfluidics-Based Biochips Fei Su & Krishnendu Chakrabarty Electrical and Computer Engineering Duke University

Motivation „

„ „

Application to clinical diagnostics, e.g., healthcare for premature infant “Bio-smoke alarm” to counter bioterrorism Massive parallel DNA analysis; automated drug discovery Shrink Microfluidics-Based Biochip Microfluidic Lab-on-Chip

Conventional Biochemical Analyzer 2

Microfluidics „

„

Continuous-flow biochips: Permanently etched microchannels, micropumps and microvalves Digital microfluidic biochips: Manipulation of liquids as discrete droplets (digital microfluidics)

(University of Michigan) 1998

(Duke University) 2002 3

Integration of microfluidics: one of the systemlevel design challenges (≤ 50nm/beyond 2009) 2003 International Technology Roadmap for Semiconductors (ITRS) Heterogeneous SOCs -Mixed-signal -Mixed-technology

Analog & RF blocks

MEMS components

CAD support needed for biochip design

Fluidic components

Digital blocks

4

Outline „ „ „ „

Motivation Background Related prior work Architectural-level synthesis for digital microfluidic biochips „ „ „

„ „

Sequencing graph model Mathematical programming model Heuristics for scheduling problem

Simulation experiments Conclusions 5

Background „ „

Novel microfluidic platform invented at Duke University Droplet actuation is achieved through an effect called electrowetting 

Electrical modulation of the solid-liquid interfacial tension

No Potential A droplet on a hydrophobic surface originally has a large contact angle.

Applied Potential The droplet’s surface energy increases, which results in a reduced contact angle. The droplet now wets the surface. 6

Background (Cont.) „

Actuation principle of digital microfluidics Droplet Transport A droplet can be transported by removing a potential on the current electrode, and applying a potential to an adjacent electrode.

7

Background (Cont.) „

Digital microfluidics-based biochips TRANSPORT TRANSPORT

DISPENSING DISPENSING

MIXERS MIXERS

„ INTEGRATE

Digital Microfluidic Biochip

„

REACTORS REACTORS

DETECTION DETECTION

Basic microfluidic functions (transport, splitting, merging, and mixing) have already been demonstrated on a 2-D array Digital microfluidics-based biochip is a high reconfigurable system

8

Background (Cont.) „

The in-vitro measurement of glucose in human physiological fluids Glucose + H 2 O + O 2 Glucose  Oxidase → Gluconic Acid + H 2 O 2 2H 2 O 2 + 4 - AAP + TOPS Peroxidase  → Quinoneimi ne + 4H 2 O

9

Background (Cont.) „

Digital microfluidics-based biochip used in glucose measurement

Dispensing/Transportation: Sample droplet (glucose) and reagent droplet (glucose oxidase, peroxidase, 4-AAP and TOPS), are dispensed into the microfluidic system from reservoirs.

Length of the control electrode L = 1.5mm Height between two plates H = 475nm Thickness of insulator layer (parylene C) = 800nm Thickness of hydrophobic film (Teflon AF) = 60nm

Mixing: Sample droplet and reagent droplet are mixed in a mixer (i.e. 2x2 array mixer). Optical Detection: Assay result (quinoneimine) is detected by a green LED and a photodiode. 10

Background (Cont.) „

„

Detection of lactate, glutamate and pyruvate has also been demonstrated. Biochip used for multiplexed in-vitro diagnostics on human physiological fluids

Fabricated microfluidic array used in multiplexed biomedical assays. 11

Synthesis Methodology „

Full-custom design Æ Top-down system-level design

ƒ Scheduling of operations ƒ Binding to functional resources ƒ Physical design

12

Related Prior Work „

Synthesis of integrated circuits: well-studied problem

„

MEMS simulation & synthesis tools

„

CAD tools for microfluidic biochips „ „

Physical-level simulation: CFD-ACE+, FlumeCAD System-level design: CoventorWare (targeted at continuous flow system)

„

DNA array (ICCAD’03)

„

Special session on BioMEMS CAD at DAC’04 13

Architectural-Level Synthesis „

Sequencing graph model „

Multiplexed in-vitro diagnostics

Sample

Reagent

Enzymatic Assay

Plasma: S1

R1

Glucose Measurement

Serum: S2

R2

Lactate Measurement

Urine : S3

R3

Pyruvate Measurement

Saliva: S4

R4

Glutamate Measurement

14

Sequencing Graph Model (Cont.) „

Node representing the input operation Sj

Rj Ij

Ij+m

(Dispensing sample Sj, j=1,…, m) (Dispensing reagent Rj, j=1,…, n)

Assumption 1: The time required to generate and dispense droplets from the reservoir is determined mainly by the system hardware parameters 15

Sequencing Graph Model (Cont.) „

Node representing different types of mixing operations S1

Ri M1

(Mixing of sample S1 and reagent Ri, i=1, …, n)

S2

Ri M2

(Mixing of sample S2 and reagent Ri, i=1, …, n)

Sm …...

Ri Mm

(Mixing of sample Sm and reagent Ri, i=1, …, n)

Assumption 2: The time required for complete mixing mainly depends on the viscosity of the sample

16

Sequencing Graph Model (Cont.) „

Node representing the detection operations Si +R2

S i+R1 D1 Optical detection of Assay 1, e.g., glucose assay

Si+Rn …...

D2

Optical detection of Assay 2, e.g., lactate assay

Dn

Optical detection of Assay n, e.g., glutamate assay

Assumption 3: The type of enzymatic assay determines the optical detection time.

17

Sequencing Graph Model (Cont.) Assumption 4: In contrast to the above operations, droplet movement on a digital microfluidic array is very fast. We can ignore the droplet movement time for scheduling assay operations.

Size view

Top view 18

Sequencing Graph Model (Cont.) Input operations: 2mn Nodes

NOP

S1

S1

I1

……

I1

…

……

……

Sm

Im

……

……

……

Sm

Im

……

……

R1

Im+1

Rn

Im+n

………

…

……

R1

Im+1

Rn ……

Im+n

1 ………

2mn+1

M1

………

…………

………

M1

………

3mn+1

D1

…………

…………

………

Mm

………

Dn …

…………

…

…………

………

Mm

3mn

………

D1

…………

Dn

4mn

…

NOP

Sequencing graph model of a multiplexed bioassays

2mn

Mixing operations: mn Nodes Detection operations: mn Nodes

Time Step 15 M1 Storage unit is required during this time period

25 30 D1

19

Mathematical Programming Model Objective „

First define a binary variable

 1 if operation vi starts at time slot j. X ij =   0 otherwise „

Starting time of operation vi :

Constraints Dependency constraints

„

Stj ≥ Sti + d(vi) if there is a dependency between vi and vj

Resource constraints

„

St i = ∑ j × X ij

Nr reservoirs/dispensing ports assigned to each type of fluid (Nr = 1)

j =1

„

Completion time of operation: C = max {Sti + d(vi) : vi ∈D1, …, Dn}

„

Objective function: minimize C

Reservoirs/dispensing ports

„

T

∑ X ij ≤ 1,

i:vi ∈I1

…

∑ X ij ≤ 1

: 1≤ j≤ T

i:vi ∈I m + n

Reconfigurable mixers and storage units

„

Nmixer(j) + 0.25 Nmemory(j) ≤ Na

1≤ j≤T

Optical detectors

„

Nd detectors are assigned to each bioassay (Nd = 1)

∑

i:vi ∈D1

j

∑ X ij ≤ 1, …i:v∑ ∈D

l = j − d ( vi )

i

n1

j

∑

X ij l = j − d ( vi )

≤ 1 1≤ j≤ T 20

Mathematical Programming Model (Cont.) „

Evaluated for a problem of the modest size: Plasma and serum are sampled and assayed for glucose, lactate and pyruvate measurements; i.e., m = 2, n = 3 Assume Nr = Nd = 1, and Na = 4

„

„

Time step

S1

S1

S1

S2

S2

S2

R1

R2

R3

R1

R2

R3

I1

I1

I1

I2

I2

I2

I3

I4

I5

I3

I4

I5

1

2

3

4

5

6

7

8

9

10

11

12

1 2

3 4 5 6

d(Ii)=1 13

19

M1

D1

14

20

M1

D2

15

21

M1

D3

16

22

M2

D1

17

23

M2

D2

18

24

M2

D3

d(M1)=5 d(M2)=3 d(D1)=5 d(D2)=4 d(D3)=6

7 8

Reservoirs

Reconfigurable Mixers

for S1 for S2 for R1 for R2 for R3

1

6

12

7

18

8

2 3

9

4

5

13

14

10 11

9 10

15

24

16 17

19 20

11 12 13 14 15

NOP

Optical Detectors for D1 for D2 for D3

22

21 23

16 17

Optimal schedule obtained by using integer linear programming Completion time is 17 time-slots; i.e., 34 seconds. 21

Heuristics for the Scheduling Problem „

Heuristic algorithms „

Modified List Scheduling algorithm (M-LS) „ „

„

Extend well-known List Scheduling algorithm Modified to handle the reconfigurable resources (i.e., mixer and storage units)

Heuristic based on a Genetic algorithm (GA) „ „ „

Representation of chromosome (random keys) Ad-hoc schedule construction procedure Evolution strategy

22

Simulation Experiments „

Lower bound (LB)

LB = m×max{d(D1),… d(Dn)}+min{d(M1),… d(Mm)}+d(Ii)+1

Upper bound (UB) UB = m× max{d(D1),…d(Dn)}+k×max{d(M1),…d(Mm)}+max(m, n)×d(Ii)+ 1

„

Mixer with Detector with Reservoirs smallest d largest d 1

Reservoirs

Phase I

Input operations: Max duration = max(m, n)

Min{d(M 1), …, d(Mm)}

Worst case: 2mn storage units needed Step 1: NMix1 mixing operations scheduled

Phase II

NMix1 +0.25(2mn-2NMix1 )≤Na Æ NMix1≤2Na-mn

Mixing operations: Max duration = k×max{d(M1), …, d(Mm )}

m×Max{d(D1), …, d(Dn)}

Step 2: NMix2 mixing operations scheduled NMix2 +0.25NMix1+0.25(2mn2 NMix1-2NMix2)≤Na Æ NMix2≤2Na-mn+0.5NMix1 Step k: NMix k mixing operations scheduled

Phase III Detection operations: Max duration = m×max{d(D1), …, d(Dn)}

(a)

(b)

23

Simulation Experiments (Cont.) „

Five examples (four samples) S1: Plasma, S2: Serum, S3:

Urine, S4: Saliva, Assay1: Glucose assay, Assay2: Lactate assay, Assay3: Pyruvate assay, Assay4: Glutamate assay Example

Description

Example 1 (Nr=Nd=1,Na=3) m=2, n=2

S1 and S2 are assayed for Assay1 and Assay2.

Example 2 (Nr=Nd=1,Na=4) m=2, n=3

S1, and S2 are assayed for Assay1, Assay2, and Assay3.

Example 3 (Nr=Nd=1,Na=5) m=3, n=3

S1, S2, and S3 are assayed for Assay1, Assay2, and Assay3.

Example 4 (Nr=Nd=1,Na=7) m=3, n=4

S1, S2, and S3 are assayed for Assay1, Assay2, Assay3 and Assay4. S1, S2, S3 and S4 are assayed for Assay1, Assay2, Assay3 and Assay4.

Example 5 (Nr=Nd=1,Na=9) m=4, n=4

24

Simulation Experiments (Cont.) Simulation results Example

Opt

LB

UB

M-LS

GA

Example 1

15

15

23

17

15

Example 2

17

17

25

19

17

Example 3

N/A

23

47

26

25

Example 4

N/A

23

43

27

26

Example 5

N/A

29

59

35

34

1.4 1.2

Ratio of Heuristic/Lower Boun

„

1 0.8

GA/LB

M-LS/LB

0.6 0.4 0.2 0 1

2

3 Example

4

5

25

Conclusions „

„

„

A system design methodology to apply classical architectural-level synthesis techniques to digital microfluidics-based biochips An optimal strategy based on integer linear programming for scheduling assay operations under resource constraints Two heuristic techniques that scale well for large problem instances „ „

„

M-LS: computationally more efficient GA: yields lower completion times for bioassays

A clinical diagnostic procedure used to evaluate the proposed methodology 26