Connectionists: How the brain overcomes the curse of dimensionality: a CMOS dynamic programming circuit model

[Chi-Sang Poon]

Paper download: http://dspace.mit.edu/handle/1721.1/59393

 

A CMOS Current-Mode Dynamic Programming Circuit 

Mak, Terrence; Lum, Kai-Pui; Ng, H. S.; Rachmuth, Guy; Poon, Chi-Sang 

IEEE Transactions on Circuits and Systems I: Regular Papers, PP.99 (2010):
1-12. C Copyright 2010 IEEE

 

Abstract: Dynamic programming (DP) is a fundamental algorithm for complex
optimization and decision-making in many engineering and biomedical systems.
However, conventional DP computation based on digital implementation of the
Bellman-Ford recursive algorithm suffers from the "curse of dimensionality"
and substantial iteration delays which hinder utility in real-time
applications. Previously, an ordinary differential equation system was
proposed that transforms the sequential DP iteration into a continuous-time
parallel computational network. Here, the network is realized using a CMOS
current-mode analog circuit, which provides a powerful computational
platform for power-efficient, compact, and high-speed solution of the
Bellman formula. Test results for the fabricated DP optimization chip
demonstrate a proof of concept for this solution approach. We also propose
an error compensation scheme to minimize the errors attributed to nonideal
current sources and device mismatch.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://mailman.srv.cs.cmu.edu/mailman/private/connectionists/attachments/20101103/bbbb0b7d/attachment-0001.html