6.004-25,Summary of Computation Structures

MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L25 – Wrapup Lecture 1 6.004 – Spring 20095/12/09Computer Architecture: Exciting Times Ahead! Prediction is very difficult, especially about the future. --Neils BohrThe best way to predict the future is to invent it. --Alan Kaymodified 5/4/09 10:17L25 – Wrapup Lecture 2 6.004 – Spring 20095/12/09You’ve mastered a lot… Fets & voltages Logic gates Combinational logic circuits Combinational contract: discrete-valued inputs complete in/out spec. static discipline Acyclic connections Summary specification Design: sum-of-products simplification muxes, ROMs, PLAs Storage & state Dynamic discipline Finite-state machines Metastability Throughput & latency Pipelining Sequential logic L25 – Wrapup Lecture 3 6.004 – Spring 20095/12/09… a WHOLE lot … Sequential logic +4+C*4ASEL01Data Memory RDWDAdrR/WWDSEL012WA Rc <25:21> 01XP PCSELPCJT+4InstructionMemoryADRb: <15:11> Ra <20:16> RA2SELRc <25:21> +RegisterFileRA1RA2RD1RD2BSEL01C: <15:0> C: <15:0> sign-extended ZALUABJTWA WDWEC: <15:0> << 2 sign-extended ALUFN Control LogicZASELBSELPCSELRA2SELWDSELALUFN Wr +401Wr 01234XAdr ILLOPWASEL WASEL IRQWERFWERF00CPU Architecture Computing Theory Instruction Set Architectures Beta implementation Pipelined Beta Software conventions Memory architectures ?Interconnect Virtual machines Interprocess communication Operating Systems Real time, Interrupts Parallel Processing Computer Systems MEMMEMCPUDISK I/OI/OL2 $ Graphics I/O“AGP” bus L25 – Wrapup Lecture 4 6.004 – Spring 20095/12/096.035 (U, ) Computer Language Engineering What’s next?Some follow-on options…Software Hardware 6.374 (G, ) Analysis and Design of Digital Integrated Circuits6.033 (U, ) Computer System Engineering 6.111 (U, ) Introductory Digital Systems Laboratory LA for 6.004 UROPSpecial Topics 6.823 (G, ) Computer System Architecture 6.115 (U, ) Microcomputer Project Laboratory 6.375 (U, ) Complex Digital System Design L25 – Wrapup Lecture 5 6.004 – Spring 20095/12/09Things to look forward to… 6.004 is only an appetizer! AlgorithmsArithmetic Signal Processing Language implementation Processors Superscalars Deep pipelines Multicores Systems Software Storage Virtual Machines Networking Languages & Models Python/Java/Ruby/… Objects/Streams/Aspects Networking Tools Design Languages FPGA prototyping Timing Analyzers L25 – Wrapup Lecture 6 6.004 – Spring 20095/12/09Verilog example: Beta Register File //2-read, 1-write 32-location register filemodule regfile(ra1,rd1,ra2,rd2,clk,werf,wa,wd);input [4:0] ra1;//address for read port 1 (Reg[RA]) output [31:0] rd1;//read data for port 1input [4:0] ra2;//address for read port 2 (Reg[RB], Reg[RC] for ST) output [31:0] rd2;//read data for port 2input clk;input werf;//write enable, active highinput [4:0] wa;//address for write port (Reg[RC])input [31:0] wd;//write data reg [31:0] registers[31:0];//the register file itself(local) //read paths are combinational, check for reads from R31 assign rd1 = (ra1 == 31) ? 0 : registers[ra1];assign rd2 = (ra2 == 31) ? 0 : registers[ra2]; //write port is active only when WERF is asserted always @(posedge clk)if (werf) registers[wa] <= wd;endmoduleL25 – Wrapup Lecture 7 6.004 – Spring 20095/12/09PCmodule pc(clk,reset,pcsel,offset,jump_addr, branch_addr,pc,pc_plus_4); input clk;input reset;//forces PC to 0x80000000 input [2:0] pcsel;//selects source of next PC input [15:0] offset;//inst[15:0] input [31:0] jump_addr;//from Reg[RA], used in JMP instruction output [31:0] branch_addr;//send to datapath for LDR instruction output [31:0] pc;//used as address for instruction fetch output [31:0] pc_plus_4;//saved in regfile during branches, JMP, traps reg [31:0] pc;wire [30:0] pcinc; wire [31:0] npc; //the Beta PC increments by 4, but won’t change supervisor bit assign pcinc = pc + 4; assign pc_plus_4 = {pc[31],pcinc}; //branch address = PC + 4 + 4*sxt(offset) assign branch_addr = {0,pcinc + {{13{offset[15]}},offset[15:0],2'b00}}; assign npc = reset ? 32'h80000000 : (pcsel == 0) ? {pc[31],pcinc} ://normal (pcsel == 1) ? {pc[31],branch_addr[30:0]} ://branch (pcsel == 2) ? {pc[31] & jump_addr[31],jump_addr[30:0]} ://jump (pcsel == 3) ? 32'h80000004 : 32'h80000008;//illop, trap //pc register, pc[31] is supervisor bit and gets special treatment always @(posedge clk) pc <= npc;endmodule L25 – Wrapup Lecture 12 6.004 – Spring 2009 5/12/09 The Crystal Ball some trends in computer evolution •Technology shrinks •30% linear shrink/generation •Cheaper, faster, lower power •Multicores (SMP, Tiled NUMA, …) •Superscalar/SMT pipelines •Power management •Reconfigurable processing/interconnect •VLIW, SIMD influences L25 – Wrapup Lecture 13 6.004 – Spring 2009 5/12/09 2010 Architecture? I/O Embedded DRAM Embedded DRAM Off-chip DRAM Tiles Tiled (VLIW/reconfigurable/vector) machines become popular in systems with resource constraints (hardware cost, low power, hard real time) •10 GHz processor clock •5 GHz network clock •128 processing tiles •>5 TFLOPS peak (32b FLOPS) •>40 TOPS peak (8b OPS) •1GB on-chip DRAM •100 GB/s off-chip DRAM interface •100 GB/s I/O •25x25mm2 in 0.045μm CMOS Giant uniprocessors (maybe with SMT) remain popular in markets where software is the main expense. L25 – Wrapup Lecture 14 6.004 – Spring 2009 5/12/09 Thinking Outside the Box Will computers always look and operate the way computers do today? Some things to question: •Well-defined system “state” •Programming •Silicon-based logic •Logic at all Si Boolean Logic MOSFET transistors Synchronous Clocked Systems Von Neumann Architectures L25 – Wrapup Lecture 15 6.004 – Spring 2009 Our programming hangup Our machines slavishly execute sequences of instructions. Does a cerebellum? A society? A beehive? An MIT student? Is there an engineering discipline for building goal-oriented systems from goal-oriented components? Is learning an alternative to programming? Adaptive Memory PUNISH L25 – Wrapup Lecture 16 6.004 – Spring 2009 5/12/09 Wet Computers 1) The most reliable, sustainable, efficient, and smartest??? machines that we know of are biological 2) Fined tuned through millions of years of evolution 3) The assembly, repair, and operation “instructions” for multi-billion element machines are “digitally” encoded in a single molecule 4) We are just beginning to understand the “gates” and the “machine language” I wonder if 2289384-1 is prime? L25 – Wrapup Lecture 17 6.004 – Spring 20095/12/09DNA Chips (DNA probes or microarrays) Leverages VLSI fabrication techniques (photolithography)Use PCRs (polymerase chain reactions) to make an exponential number of DNA copiesMechanically bind specific “tagged” gene sequences onto a patterned substrate Expose to bath of denatured nucleotides (separated and diced up pieces of DNA) Look for phosphorescent markers Medical applications are obvious, but what does it have to do with computation? Micro “vials” of a gene sequence Questions: What inputs satisfy f(x1,x2,…xN) =1. We can reliably reslice and recombine (state machines?) L25 – Wrapup Lecture 18 6.004 – Spring 20095/12/09Can we Program Microbes? DNA = program Protein synthesis = gates? Can we “engineer” organisms to perform computations for us? Can we make a “standard cell library” offering digital building blocks from DNA sequences? This is alien thinking for biologist, but standard fare for systems designers F(n) = n * F(n-1); F(0) = 1 L25 – Wrapup Lecture 19 6.004 – Spring 20095/12/09Computing at the limit At the particle level nature behaves very strangely… Far separated particles can be entangled -electron spins -photon polarizations -magnetic fields They can be simultaneously in either state(so long as you don’t look). The act of looking at them (measuring, or observing them) forces the entangled particle into one of its states. Strangely enough, it is believed that we can use such entangled particles in computations w/o disturbing them. L25 – Wrapup Lecture 20 6.004 – Spring 20095/12/09Quantum Computing? Classic computers perform operations on strings of bits (0s and 1s). A quantum computer would be able to compute on bits (qubits) that can be simultaneously in either state. F(0< x < 220) = x * 371 F(?) = 197001 Classic computer: (with a dumb algorithm) Search through all 220permutations Quantum computer: Insert 20 qubits, select the desired answer, then look back and see what the qubits resolved to… L25 – Wrapup Lecture 21 6.004 – Spring 20095/12/09The Dilemma •We have no clue how to build a practical quantum computer •Currently, quantum computing is merely a fantasy of theoreticians•What other problems can a quantum computer solve more efficiently than a classic computer? A SUBTLE Reminder: Turing, Church, Post, Kleene, and Markov really “invented” most of modern day computer science long before a “practical” implementation. L25 – Wrapup Lecture 22 6.004 – Spring 20095/12/096004: The Big Lesson Engineering Abstractions: •Understanding of their technical underpinnings•Respect for their value •Techniques for using them But, most importantly: •The self assurance to discard them, in favor of new abstractions! Good engineers use abstractions; GREAT engineers create them! You’ve built, debugged, understood a complex computer from FETs to OS… what have you learned? L25 – Wrapup Lecture 23 6.004 – Spring 20095/12/09THE END! Pens, pencils, paper they attempt to solve problems that teachers set forth. The only problem with Haiku is that you just get started and then