Uncovering the Intriguing World of Computational Models and Quantum Phenomena

Montek Singh COMP740 Nov 7, 2016

Quantum dot cellular automata (QCA) Electrostatic QCA Magnetic QCA Probabilistic Computing Multicore/Many-core systems On-Chip Networks Computing using DNA DNA as the computer DNA as the assembler of a computer Neuromorphic Computing

Discrete model studied in computability grid made up of cells each cell can be in one of finite number of states each cell has a defined neighborhood at each new time step, the state of a cell is determined by the state of its neighborhood in prior time step Conway s Game of Life

e.g., Rule 30 e.g., Rule 110

Seashell patterns each cell s pigment controlled by activating and inhibiting activity of neighbors Conus textile

QCA proposed models of quantum computation analogous to conventional CAs but based on quantum mechanical phenomenon of tunneling Quantum dots 4-dot cell basic unit of storage and computation two states: -1 and +1 electrostatic repulsion

Wires formed by juxtaposition of cells if leftmost is controlled externally, all others align same direction like dominoes falling

Key idea is to place cells at 45 degrees w.r.t. each other Two branches used here, one can work too

Majority gate 2 out of 3 inputs determine output Can you make? AND gate OR gate

Magnetic domains regions within magnetic material with uniform magnetization separated by domain walls magnetic moments all exactly aligned responsible for magnetic behavior of ferromagnetic materials: iron, nickel, etc. What causes them? magneto-static energy is minimized Other energy terms: magnetoelastic anisotropy magnetocrystalline anisotropy Zeeman energy Magnetic domains

Magnetic domains more domains reduces magnetostatic energy but increases wall energy Single Domain (SD) 10 to 100nm is a good size

Magnetization under externally applied magnetic field (H) domains change shape and magnetic moments re-orient walls shift or disappear even physical shape of material can change somewhat! called magnetostriction useful in actuators and sensors in strong enough field, all domains aligned minimizes Zeeman energy

Operate at reduced voltage more noise but lesser energy consumption Where is this acceptable? Where could this be even desirable?

Thermal noise makes any switch noisy probability of error depends on thermal noise vs. operating voltage

energy required goes up exponentially with prob. of correctness

Supply reduced voltage to adder gates fine-grain: each stage receives own voltage coarse-grain: use binning

Energy-correctness tradeoff example

Two or more CPU cores on a single die typically share L2 cache typically separate L1 caches share main memory

What was happening before c. 2010? What started happening c. 2010? Why?

Three main technological reasons Memory Wall increasing gap between CPU and memory speeds no longer makes sense to simply make CPU faster ILP Wall increasing difficulty in finding enough parallelism in single stream of instructions tried hyper-threading already Power Wall increasing frequency was increasing power density without so much increase in performance poses big manufacturing problems

(NOC = Network-on-a-chip)

Communication fabric between components/cores

Several topologies

Grid-structured NoC

in terms of OSI layer model of networking

Two different technologies DNA as biochemical computer DNA molecules encode data enzymes, probes etc. manipulate data DNA used to assemble electronic computer DNA molecules used as scaffolding nanoscale electronic components piggyback DNA assembles the computer

I was fascinated. With my own hands, I was creating DNA that did not exist in nature. Leonard M. Adleman Scientific American, August 1998

To build a computer, only two things are really needed a method of storing information a few simple operations for acting on that information Turing machine Is DNA good enough? great way to store the blueprint of life enzymes (polymerases and ligases) can operate Is this enough? YES!

Hamiltonian Path Problem given: a directed graph, G given: specified start and end nodes, s and t definition: Hamiltonian path is one that goes from start node to end node, passing through each remaining node exactly once decide: whether a Hamiltonian path exists for <G,s,t> Like all good problems, this one is NP-complete

Given graph with n vertices, 1. Generate a set of random paths through the graph 2. For each path: a. check if path has correct start and end nodes b. check if path passes through exactly n nodes c. Remove path if it fails any of these checks 3. If set is not empty, report that a Hamiltonian path exists. check if each vertex is visited

Hamiltonian Path Problem 7 cities, 14 nonstop flights takes about a min for most of us Smaller problem 4 cities for illustration

Use DNA fragments to code cities and flights each city X has two parts to its name (X1X2) and complement (X 1X 2) a flight also has 2 parts flight from X1X X2 2 to Y Y1 1Y2 has sequence: (X X2 2Y Y1 1)

Synthesize: complements of city names (X 1X 2) flights (X2Y1) A pinch of each has 1014 molecules throw them all into a test tube add water, ligase, salt one drop, one second!

Each flight bonds only with complements of its start and end cities: flights (X2Y1) bonds with (X 1X 2) and (Y 1Y 2) ligase seals fragments Sequences grow: Atlanta-Boston Atlanta-Boston-Chicago

1014 or so parallel computations! All paths created at once

Pioneering work by Chris Dwyer et al. PhD at UNC; now faculty at Duke Key Idea: Exploit constraints on DNA bonding to design DNA sequences that will only come together in predictable ways Piggy back components of interest on top of DNA: transistors, wires, etc. Terminology: functionalization: attaching DNA strand to a component of interest

3 distinct DNA-functionalized objects assemble into a triad if sequences are carefully chosen

Extend idea to 2D grid Protein attached to form the pattern CAD