DOC PREVIEW
Princeton COS 116 - Lecture

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Finite State Machines (FSMs) and RAMs and inner workings of CPUs 3/27/2008COS 116Instructor: Sanjeev AroraRecap• Combinational logic circuits: no cycles, hence no “memory”• Sequential circuits: cycles allowed; can have memory as well as “undefined”/ambiguous behavior•Clocked sequential circuits: Contain D flip flops whose“Write” input is controlled by a clock signalR-S Flip-Flop(corrected slide)SRMForbidden toturn off bothSet and Resetsimultaneously(value is“ambiguous”)Recap: D Flip FlopBasic Memory Block – stores 1 bit.DWMIf we “toggle” the write input (setting it 1 then setting it 0) then M acquires the value of D.“Timing Diagram”5V0VTimeD5V0VTimeW5V0VTimeMDWMFSMs (of Moore Type)Finite number of statesMachine can produce outputs, these depend upon current state onlyMachine can accept one or more bits of input; reading these causes transitions among states.ClosedOpenDetected PersonNo Person DetectedDetected PersonNo Person Detected“Automatic Door”Discussion TimeHow can we implement a FSM using logic gates etc.?•If number of states = 2k then represent “state” byk boolean variables.•Identify number of input variables• Write truth table expressing how “next state” is determined from “current state” and current valuesof the input.•Express as clocked synchronous circuit.What are some examples of FSMs in the Hayes article?Example: 4-state machine; 1 bit of input; No outputState variables: P, QInput variable: DNext value of P = (P+Q). DNext value of Q = PWhat is its state diagram?Implementation: General SchematicInputsCircuit to computenext stateFlip flops(memoryelements)Circuit tocomputeoutputsCLKK Flip flops allow FSM to have 2K statesImplementing door FSM as synchronous circuitINPUTSTATE0 = No Person Detected1 = Person Detected0 = Door Closed1 = OpenClosedOpenDetected PersonNo Person DetectedDetected PersonNo Person DetectedClosedOpenDetected PersonNo Person DetectedDetected PersonNo Person Detected010111101000Next StatePresent StateInputImplementation of door FSM (contd)DWMINPUTCLOCK0 = No Person Detected1 = Person Detected0 = Door Closed1 = OpenSTATEOther examples of FSMsSisyphusBrook’s Genghis (51 FSMs) (see p. 46 in our text)Human Soul a la Aquinas (see Handout)Aside: Portion of Genghis AFSM Network [Parker’94]IRsensorsprowlbeta forcewalkfor/bakpitchbetabalanceup legtriggerleg downsteerbeta posfeeleralphacollidealphaadvancealphabalancealpha posSSSIDIreceive input from sensorscontrol actuatorsduplicated twiceunique; “central control”Next….Random Access Memory (RAM)Memory where each location has an addressRecall from last lecture: “Register” with 4 bits of memoryHow can youset up an addressingsystem for large banks of memory?RAMRAM2K bits;bank offlipflopsK Address BitsDataWriteRAMK Address BitsDataReadIf 4 locations, “address” has 2 bitsAddressClockTo RAM’s“Clock” inputRAM: Implementing “Write”RAMDecoder(Demux)DataThe decoder selects which cell in the RAM gets its “Write” input toggledK-bit address(in binary)Clock(simple combinationalcircuit; see logic handout)Ram: implementing “Read” RAMMultiplexerDataThe multiplexer is connected to all cells in the RAM; selects the appropriate cell based upon the k-bit addressK-bit address(in binary)(simple combinationalcircuit; see logic handout)Next, the secret revealed... How computers execute programs.CPU = Central Processing UnitScribbler Control Panel ProgramMachine Executable CodeF5“Download to Robot”(Compilation)•T-P programs representedin binary• .exe files in the Wintel world Similar to:Point 1: Programs are “translated”into “machine language”; this iswhat’s get executed.Greatly simplified view of modern CPUs.Program (in binary)stored in memoryMemory RegistersArithmetic and Logic Unit(ALU)Control FSMLots of Custom HardwareInstruction PointerRAMExamples of Machine Language InstructionsAdd contents of Register 3 and Register 7 and store in Register 12ADD 3 7 12If register 4 has a number > 0 set IP to 35876JUMP 4 35876Read Location 67432 from memory and load into Register 3LOAD 3 67432Stored in binary (recall Davis’s binary encoding of T-P programs)Different CPUs have different machine languagesIntel PentiumPower PCPalmpilot, etc.“Backwards Compatibility” – Pentium 4’s machine language extends Pentium 2’s machine languageMachine languages now allow complicated calculations (eg for multimedia, graphics) in a single instructionExample: Intel press releaseSANTA CLARA, Calif., June 28, 2004 - Intel Corporation today announced availability of a new Intel® Xeon™ processor-based platform and a host of new products and technologies for its Intel Xeon processor family that significantly boost performance, memory and graphics capabilities for workstation platforms. Workstations will benefit from rich set of new technologies that address the increasingly data-hungry systems and software applications that crave performance for a range of functions such as financial and scientific data modeling to digital filmmaking and design automation.Main InsightComputer = FSM controlling a larger (or infinite) memory.Meet the little green man…The Fetch – Decode – Execute FSMExecuteDecodeFetchFetch – Decode – Execute FSM“Fetch”IP IP + 1DecodeExecuteADD InstructionJUMP InstructionGo to nextinstructionCPU as a conductor of a symphonyNetwork CardCPUSound CardCD-ROMVideo Card“BUS” e.g., PCIBus: “Everybody hears everybody else”How an FSM does “reasoning” “If left infrared sensor detects a person, turn left”L = 0L = 1T =1T= 0Speculation: Brain as FSM?• Network (“graph”) of 100 billion neurons; each connected to a few thousand others• Neuron = tiny Computational Element; “switching time” 0.01 s• Neuron generates a voltage spike depending upon how many neighbors are spiking.Discussion:How would you implement a Turing-Post program with a digital circuit? 1.PRINT 0 2. GO RIGHT 3. GO TO STEP 1 if 1 SCANNED 4. GO TO STEP 1 if 0 SCANNED 5. STOPAssume “PRINT” and “SCAN” as basic


View Full Document

Princeton COS 116 - Lecture

Documents in this Course
Lecture 5

Lecture 5

15 pages

lecture 7

lecture 7

22 pages

Lecture

Lecture

32 pages

Lecture

Lecture

16 pages

Midterm

Midterm

2 pages

Lecture

Lecture

23 pages

Lecture

Lecture

21 pages

Lecture

Lecture

24 pages

Lecture

Lecture

22 pages

Lecture

Lecture

28 pages

Lecture

Lecture

21 pages

Lecture

Lecture

50 pages

Lecture

Lecture

19 pages

Lecture

Lecture

28 pages

Lecture

Lecture

23 pages

Lecture

Lecture

21 pages

Lecture

Lecture

19 pages

Lecture

Lecture

22 pages

Lecture

Lecture

21 pages

Logic

Logic

20 pages

Lab 7

Lab 7

9 pages

Lecture

Lecture

25 pages

Lecture 2

Lecture 2

25 pages

lecture 8

lecture 8

19 pages

Midterm

Midterm

5 pages

Lecture

Lecture

26 pages

Lecture

Lecture

29 pages

Lecture

Lecture

40 pages

Lecture 3

Lecture 3

37 pages

lecture 3

lecture 3

23 pages

lecture 3

lecture 3

20 pages

Lecture

Lecture

21 pages

Lecture

Lecture

24 pages

Lecture

Lecture

19 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?