2004 Computing Beyond Silicon Summer School

  . home
  . application
  . speakers
  . schedule:

reading | questions

  . faqs
  . final report

  . Caltech home
  . Caltech Computer Science
  . Caltech IST
  . Caltech E&AS Division


  CBSSS poster
  2004 poster
(8.5x11in PDF, 492K)





Questions CBS3 2002 | Final Report CBS3 2002

Bacon | DeHon | Savage | Snider | Yurke

Wednesday, June 16

Lecturer: John Savage Topic: Models of Computation

a. Determine the number of Boolean functions on n variables. Count the number of circuits containing k or fewer gates. Use these facts to show that the most complex Boolean function on n variables has circuit size at on the order of 2^n/n.

b. Design an FSM to add 1 to a binary number that is supplied as a binary sequence, less significant digit first.

c. Design a TM to recognize strings of the form ww^R where w is a binary string and w^R is its reverse.

d. Design a 2D mesh to multiply two n x n matrices in O(n) steps.

e. Show that a CRCW PRAM can be programmed to compute the value of a Boolean function in a constant number of steps.

f. Give a proof that the basis {AND, OR} is not complete.

g. Show that every Boolean function can be expanded as the EXCLUSIVE OR of the AND of literals (variables or their complements). Show that in this expansion OR requires an exponential number of terms.

h. Show how addition of two binary numbers can be realized by a one-tape Turing machine using two tracks on its tape, one containing data and a second containing markers.

i. Give a complete design of a universal Turing machine. This requires that a representation of TMs be decided upon in advance.

j. Describe in detail the alphabet for strings that are configurations of Turing machines.

k. Complete the proof that a TM does not exist to solve the Halting Problem.

go to top of page

Friday, June 18

Lecturer: Bernard Yurke Topic: DNA: Structure, Energetics, Kinetics, and Machines
[see also reading]

Project: Devise a DNA-based method to evaluate arbitrary Boolean functions employing only hybridization and strand displacement. For readout, use a set of fluorescently labeled DNA strands and a hybridization plate that has an array of DNA strands with sequences you specify.

Hint at a possible approach: Consider a patch a on a hybridization plate to which DNA strands with base sequence A have been attached. If one introduces strands having the base sequence cAcB where cA denotes the complement of A and cB denotes the complement of B then the cAcB strands will hybridize to the DNA on patch a. If one then introduces dye labeled strands B they will hybridize to the sequence cB of the cAcB strands. Consequently, after the hybridization plate is washed to remove excess B and cAcB, patch a will show fluorescence. Patch a will fluoresce only if it has DNA with sequence A and if strands B are present. Strands cAcB can thus be regarded as a kind of "and" operator. They link strands A and strands B together.

go to top of page

Monday, June 21

Lecturer: Andre DeHon
[see also reading]

Project 1: 3D Adiabatic Switching:
A common concern is that the limit to computational density could come from power density rather than small feature sizes. Effects of this are already being seen in conventional MOS designs. We can contemplate 3D architectures to further extend computing density, but this will only exacrabate the power density/heat-removal problem. In theory, it should be possible to compute with zero energy using reversible operations, but adiabatic circuits will require more area than their conventional counterparts, and may need to run very slowly to provide their net benefit. How can we combine parallelism, 3D circuit construction, and adiabatic switching to increase the net computation which can be sustained in a given volume with a fixed power limit? (i.e. how can we increase the net computational density beyong traditional/naive power density limits?) * Feynman Lectures on Computation (Chapters 5 and 7.2) * S. G. Younis and T. F. Knight, Jr., "Asymptotically Zero Energy Split-Level Charge Recovery Logic," in Proceedings of the International Workshop on Low Power Design, 1994, pp. 177--182.

go to top of page

Project 2: Runtime/Programming Language Model for Unreliable Hardware:
When gates are no longer reliable, what is a reasonable compute model/runtime system/programming language for achieving reliable computations on top of unreliable compute structures? As we reach the atomic scale, it will no longer be reasonable to expect individual gates to perform 100% reliably [LLNSD]. We can use redundancy to increase the reliablity at the circuit level [e.g. VN,PIP]. We can allow architectural checking and roll-back [e.g. RAZOR, SHANGBANG]. These techniques will make the probability of errors slipping through to higher levels lower, but will not make it zero. So, how should our higher levels of system composition and design evolve to accommodate the fact that some errors will propagate up and be visible at this level?
LLNSD: http://www.cs.caltech.edu/research/ic/abstracts/

VN: @InCollection{vonneumann_unreliable_components56,
author = {John Von~Neumann},
title = {Proabilistic Logic and the Synthesis of Reliable
Organisms from Unreliable Components},
booktitle = {Automata Studies},
publisher = {Princeton University Press},
year = 1956,
editor = {Claude Shannon and John McCarthy}

author = {Nicholas Pippenger},
title = {Developments in 'The Synthesis of
Reliable Organisms from Unreliable Components'},
booktitle = {Proceedings of the Symposia of Pure Mathematics},
pages = {311--324},
year = 1990,
volume = 50



go to top of page

Tuesday, June 22

Lecturer: Dave Bacon Topic: Introduction Quantum Information: Quantum Channel Capacities
[see also reading]


The Knill-Gottesman theorem states that quantum computations done with prepared |0> states, Clifford group gate sets, and measurement in the Z basis can be efficiently simulated on a classical computer. On the other hand, it is known that using these operations we can generate Bell violations (GHZ violations) and thus there is something nonlocal about the gate sets.

Project: find a state in the Knill-Gottesman context which requires more than a bit of communication in order to simulate.

Project: find a generic protocol for the Knill-Gottesman gate set which uses as little multiparty communication as possible.

go to top of page

Wednesday, June 23

Lecturer: Gred Snider Topic: Molecular Architecture Studies I & II
[note Greg Snider's lecture I on June 23, lecture II on June 25]
[see also reading]

Nano-electronics Routing Project
Hypothetical crossbar-based architectures for nano-electronics often resemble field-programmable gate arrays (FPGAs) in that they consist of programmable "logic blocks" embedded within a programmable routing network. But unlike FPGAs, nano-electronic "chips" will contain many random defects within the crossbars, making each chip unique. Programming a single chip will require finding the defects within it, then placing and routing the desired circuit onto the chip's fabric in a way that works around those defects. To keep manufacturing costs within reasonable bounds, the entire process of defect characterization, placement and routing must be done using efficient data structures and algorithms. This project focuses on the routing portion of this problem.

Devise efficient data structures and algorithms for routing signals in crossbar architectures containing random defects. You may assume that the locations of all defective junctions are known and available to the router, and that the circuit to be implemented has already been synthesized and intelligently placed onto the crossbar fabric. You may also assume that the crossbar fabric is architecturally regular.

A general structure for representing routing networks is the routing resource graph [1, 2]. The graph uses a small data structure for each wire in the target architecture as well as a small data structure for each programmable switch that essentially points to the data structures for the two wires that the switch connects. This is reasonably efficient for small FPGAs, but can consume large amounts of memory as the size of the FPGA increases. Since most FPGAs are extremely regular in their layout and a only a very small percentage of available switches in the routing network are configured, the memory requirements can be dramatically reduced using the "Flyweight" design pattern [3] to factor out redundant connectivity information.

go to top of page

Simple algorithms for routing can be found in [4, 5].

Here are some issues to consider:

(1) Since defects are random throughout the fabric, can the Flyweight design pattern still be used?

(2) Defect rates might be in the range of, say, 5% to 15%. Can you exploit the fact that most switches in the routing network are functional in designing your data structures?

(3) Where are the likely bottlenecks in the routing network?

(4) What is a good fallback strategy if your router fails to route?

go to top of page

[1] L. McMurchie, C. Ebeling, "PathFinder: a negotiation-based performance-driven router for FPGAs," Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, pages 111 - 117.

[2] C. Ebeling, L. McMurchie, S. Hauck, S. Burns, "Placement and routing tools for the Triptych FPGA," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 3 , Issue 4 (December 1995), pages: 473 - 482.

[3] E. Gamma, R. Helm, R. Johnson, J. Vlissides, “Design Patterns,” Addison-Wesley.

[4] V. Betz, J. Rose, A. Marquardt, "Architecture and CAD for Deep-Submicron FPGAs", Chapter 4, Kluwer Academic Publishers, 1999.

[5] http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html

go to top of page



©2003-2004 California Institute of Technology


go to top of page