1 Special Topic: Emerging Technologies of ComputationMontek Singh COMP740 Nov 7, 2016
2 List of Topics 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
3 Cellular Automata Discrete model studied in computabilitygrid 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
4 Cellular Automata: Elementary examplese.g., “Rule 30” e.g., “Rule 110”
5 Cellular Automata: Biology exSeashell patterns each cell’s pigment controlled by activating and inhibiting activity of neighbors Conus textile
6 Quantum Dot Cellular AutomataQCA 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
7 QCA: wires Wires formed by juxtaposition of cellsif leftmost is controlled externally, all others align same direction like “dominoes” falling
8 QCA: inverter Key idea is to place cells at 45 degrees w.r.t. each other Two branches used here, one can work too
9 QCA: basic gate Majority gate Can you make?2 out of 3 inputs determine output Can you make? AND gate OR gate
10 Magnetic QCA
11 Basics of magnetism Magnetic domains What causes them?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
12 Basics of magnetism Magnetic domains Single Domain (SD)more domains reduces magnetostatic energy but increases wall energy Single Domain (SD) 10 to 100nm is a good size
13 Basics of magnetism 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
14 MQCA: majority gate
15 MQCA: majority gate
16 Probabilistic Computing
17 Basics of probabilistic designOperate at reduced voltage more noise but lesser energy consumption Where is this acceptable? Where could this be even desirable?
18 Probabilistic CMOS switchThermal noise makes any switch noisy probability of error depends on thermal noise vs. operating voltage
19 Energy-Correctness Tradeoffsenergy required goes up exponentially with prob. of correctness
20 Probabilistic arithmeticSupply reduced voltage to adder gates fine-grain: each stage receives own voltage coarse-grain: use binning
21 Probabilistic arithmeticEnergy-correctness tradeoff example
22 Multicore and Many-core Systems
23 What is Multicore Design?Two or more CPU cores on a single die typically share L2 cache typically separate L1 caches share main memory
24 Why Multicore? What was happening before c. 2010?What started happening c. 2010? Why?
25 Why Multicore? Three main technological reasons Memory Wall ILP Wallincreasing 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
26 Why Multicore?
27 Example: Intel i7
28 Example: ARM Cortex-A9
29 Example: NVIDIA
30 (NOC = Network-on-a-chip)On-Chip Networks (NOC = Network-on-a-chip)
31 What is an NOC? Communication fabric between components/cores
32 Communication inside a System-on-Chip (SoC)Several topologies
33 Topology Example Grid-structured NoC
34 Layers of abstraction … in terms of OSI layer model of networking
35 Topologies: Regular
36 Topologies: Irregular
37 Computing using DNA
38 Computing using DNA Two different technologiesDNA 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
39 “I was fascinated. With my own hands, I was creating DNA that did not exist in nature.”Leonard M. Adleman Scientific American, August 1998
40 How do we make DNA compute?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!
41 Let’s choose a problem! Hamiltonian Path Problemgiven: 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
42 An algorithm Given graph with n vertices,Generate a set of random paths through the graph For each path: check if path has correct start and end nodes check if path passes through exactly n nodes check if each vertex is visited Remove path if it fails any of these checks If set is not empty, report that a Hamiltonian path exists.
43 Adleman’s DNA computerHamiltonian Path Problem 7 cities, 14 nonstop flights takes about a min for most of us Smaller problem 4 cities for illustration
44 Coding the problem Use DNA fragments to code cities and flightseach city X has two parts to its name (X1X2) and complement (X’1X’2) a flight also has 2 parts flight from X1X2 to Y1Y2 has sequence: (X2Y1)
45 Coding the problem Synthesize: A pinch of each has 1014 moleculescomplements of city names (X’1X’2) flights (X2Y1) A pinch of each has molecules throw them all into a test tube add water, ligase, salt one drop, one second!
46 What happened? 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 …
47 Enormous parallelism! 1014 or so parallel computations!All paths created at once
48 Basics of DNA Self-AssemblyPioneering 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
49 Forming a triad 3 distinct DNA-functionalized objects assemble into a triad if sequences are carefully chosen
50 Forming a grid Extend idea to 2D gridProtein attached to form the pattern “CAD”
51 Basic building block: Triangular structureThree rods, anchored to a solid assembly in several steps
52 Cubic unit cell Extend the triangle into this structure
53 Electronic componentsTransistors “ring-gated field- effect transistor” RG-FET
54 Electronic componentsNanowires (gold)
55 Let’s make a gate! 2-input NAND
56 Give it some structural supportEmbed in a DNA cube of insulating unit cells gray-shaded ones are gates/wires
57 How many distinct DNA strands?Simple method: More economical method: build one face at a time: only 15 unique sequences!
58 What about larger structures?Use hierarchical assembly
59 Mimicking neurons in computationNeuromorphic Systems Mimicking neurons in computation
60 Basic Idea Departure from von Neumann computingDistributed, massively parallel Each compute element is a neuron basic functions: sum, threshold, emit spike
61 Retina Lots of photoreceptorsFeed information to brain via optical nerve
62
63
64
65 END OF SLIDES