Pin Mapping Algorithms

This page summarizes the pin mapping algorithms that have been implemented and integrated into the framework, and cites the papers that describe them in detail. Pin mapping enables control sharing, which reduces the number of control pins on the DMFB perimeter. An example is shown below.

Two electrodes may share a control pin if their simultaneous actuation does not inadvertently affect assay execution at any step of the actuation sequence. This problem has been shown to be equivalent to the Clique problem, which is NP-complete.

An example of four pin-constrained DMFBs is shown below.

Clique-based Pin Mapper

The Clique-based Pin Mapper processes the electrode activation sequence produced by the router, constructs a compatibility graph between electrdoes that could potentially share a pin, and computes a pin mapping solution by partitioning the compatibility graph into cliques.

The Clique-based Pin Mapper was introduced in the following paper.

Y. Zhao, T. Xu, and K. Chakrabarty
Broadcast Electrode-addressing and Scheduling Methods for Pin-constrained Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
30(7):986-999, July, 2011

Power-aware Pin Mapper

A Redundant Actutation Unit (RAU) is the activation of an electrode (due to pin sharing) that does not directly act on a droplet, thereby expending excess power. Under pin sharing, some RAUs are unavoidable, but power savings can be achieved by incorporating RAU minimization as an objective of the pin mapping process.

An Power-aware Pin Mapper was introduced in the following paper:

T-W. Huang, H-Y. Su, and T-Y. Ho
Progressive Network-flow based Power-aware Broadcast Addressing for Pin-constrained Digital Microfluidic Biochips
48^th Design Automation Conference (DAC)
San Diego, CA, USA, June 5-10, 2011, pp. 741-746

The Power-aware Pin Mapper employs a progressive addressing scheme in which subsets of yet-unaddressed electrodes are repeatedly selected and grouped with others for pin sharing. It models the pin count expansion using a network flow problem to limit the growth in the number of control pins while reducing power consumption.

Reliability-aware Pin Mapper

A Ground Vector (GV) is a time-step at which no electrodes are activated. Inserting GVs into an actuation sequence can mitigate the impact of trapped charge and residual charge, both of which degrade DMFB performance. Inserting a GV quickly deactivates an electrode that would otherwise be charged, thus reducing the accumulation of charge over time. 

A Reliability-aware Pin Mapper was introduced in the following paper:

T-W. Huang, T-Y. Ho, and K. Chakrabarty
Reliability-oriented Broadcast Electrode-addressing for Pin-constrained Digital Microfluidic Biochips
International Conference on Computer-Aided Design (ICCAD)
San Jose, CA, USA, November 7-11, 2011, pp. 448-455

The Reliability-aware Pin Mapper employs a progressive addressing scheme in which subsets of yet-unaddressed electrodes are repeatedly selected and grouped with others for pin sharing. It models the pin count expansion using a network flow problem to limit the growth in the number of control pins while increasing reliability.

Switching-aware Pin Mapper

Reducing the number of times each electrode is toggled on/off can reduce the likelihood of electrolysis.

A Switching-aware Pin Mapper was introduced in the following paper:

S-T. Yu, S-H. Yeh, and T-Y. Ho
Reliability-driven Chip-level Design for High Frequency Digital Microfluidic Biochips
International Symposium on Physical Design (ISPD)
Petaluma, CA, USA, March 30 - April 2, 2014, pp. 133-140

The Switching-aware Pin Mapper adds one unaddressed electrode at a time to the current electrode group being formed. It progressively relaxes the switching constraint, permitting the algorithm to discard unsuccessful electrode groupings and start over.

Routability-aware Pin Mapper

Overly aggressive pin sharing can negatively impact the PCB escape routing stage downstream. Holding the number of electrodes constant, it is generally better to route a relatively large number of short nets, the a relatively small number of long nets. As the cost of adding another PCB layer tends to be lower than the cost of adding another control pin, it can be beneficial to limit overly aggressive pin sharing.

A Routability-aware Pin Mapper was introduced in the following paper:

S. S-Y. Liu, C-H. Chang, H-M. Chen, and T-Y. Ho
ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
33(9):1316-1327, September, 2014

Contact

Please direct any questions, comments, or other inquiries to the following e-mail address: microfluidics@cs.ucr.edu

Acknowledgment

This material is based upon work supported by the National Science Foundation under Grant Numbers 1035603, 1536026, and 1545097. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.