3/30/11%1%CS%61C:%Great%Ideas%in%Computer%Architecture%(Machine%Structures)%FSMs%and%Logisim%Instructors:%Randy%H.%Katz%David%A.%PaGerson%hGp://inst.eecs.Berkeley.edu/~cs61c/sp11%3/30/11% 1%Spring%2011%NN%Lecture%#17%You%Are%Here!%• Parallel%Requests%Assigned%to%computer%e.g.,%Search%“Katz”%• Parallel%Threads%Assigned%to%core%e.g.,%Lookup,%Ads%• Parallel%InstrucYons%>1%instrucYon%@%one%Yme%e.g.,%5%pipelined%instrucYons%• Parallel%Data%>1%data%item%@%one%Yme%e.g.,%Add%of%4%pairs%of%words%• Hardware%descripYons%All%gates%funcYoning%in%parallel%at%same%Yme%3/30/11% Spring%2011%NN%Lecture%#17% 3%Smart%Phone%Warehouse%Scale%Computer%So.ware%%%%%%%%Hardware%Harness%Parallelism%&%Achieve%High%Performance%Logic%Gates%Core% Core%…%%%%%%Memory%%%%%%%%%%%%%%%(Cache)%Input/Output%Computer%Main%Memory%Core%%%%%%%%%%InstrucYon%Unit(s)%%%%%%%%FuncYonal%Unit(s)%A3+B3%A2+B2%A1+B1%A0+B0%Today%Levels%of%RepresentaYon/InterpretaYon%lw %%%$t0,%0($2)%lw %%%$t1,%4($2)%sw %%%$t1,%0($2)%sw %%%$t0,%4($2)%High%Level%Language%Program%(e.g.,%C)%Assembly%%Language%Program%(e.g.,%MIPS)%Machine%%Language%Program%(MIPS)%Hardware%Architecture%DescripCon%(e.g.,%block%diagrams)%%Compiler)Assembler)Machine)Interpreta4on)temp%=%v[k];%v[k]%=%v[k+1];%v[k+1]%=%temp;%0000 1001 1100 0110 1010 1111 0101 1000 1010 1111 0101 1000 0000 1001 1100 0110 1100 0110 1010 1111 0101 1000 0000 1001 0101 1000 0000 1001 1100 0110 1010 1111 !Logic%Circuit%DescripCon%(Circuit%SchemaCc%Diagrams)%Architecture)Implementa4on)Anything%can%be%represented%as%a%number,%%i.e.,%data%or%instrucYons%3/30/11% 4%Spring%2011%NN%Lecture%#17%Review%• Hardware%systems%are%constructed%from%Stateless%CombinaYonal%Logic%and%Stateful%“Memory”%Logic%(Registers)%• Real%world%voltages%are%analog,%but%are%quanYzed%to%represent%logic%0%and%logic%1%• Truth%table%can%be%mapped%to%gates%for%combinaYonal%logic%design%• Boolean%algebra%allows%minimizaYon%of%gates%• State%registers%implemented%from%FlipNflops%3/30/11% Spring%2011%NN%Lecture%#17% 5%Agenda%• State%Elements%• Finite%State%Machines%• Administrivia%• IntroducYon%to%Logisim%• Technology%Break%• MulYplexer%• ALU%Design%3/30/11% 6%Fall%2010%NN%Lecture%#23%Model%for%Synchronous%Systems%3/30/11% Fall%2010%NN%Lecture%#23% 7%• CollecYon%of%CombinaYonal%Logic%blocks%separated%by%registers%• Feedback%is%opYonal%• Clock%signal(s)%connects%only%to%clock%input%of%registers%• Clock%(CLK):%steady%square%wave%that%synchronizes%the%system%• Register:%several%bits%of%state%that%samples%on%rising%edge%of%CLK%(posiYve%edgeNtriggered)%3/30/11%2%Camera%Analogy%• Want%to%take%a%portrait%–%Yming%right%before%and%aler%taking%picture%• Set%up%?me%–%don’t%move%since%about%to%take%picture%(open%camera%shuGer)%• Hold%?me%–%need%to%hold%sYll%aler%shuGer%opens%unYl%camera%shuGer%closes%• Time%click%to%data%–%Yme%from%open%shuGer%unYl%can%see%image%on%output%(viewfinder)%3/30/11% Spring%2011%NN%Lecture%#17% 8%Timing%Terms%• Setup%Time:%when%the%input%must%be%stable%before%the%rising%edge%of%the%CLK%• Hold%Time:%when%the%input%must%be%stable%a.er%the%rising%edge%of%the%CLK%• “CLKNtoNQ”%Delay:%how%long%it%takes%the%output%to%change,%measured%from%the%rising%edge%of%the%CLK%3/30/11% 9%Fall%2010%NN%Lecture%#23%Maximum%Clock%Frequency%• What%is%the%maximum%frequency%of%this%circuit?%3/30/11% Fall%2010%NN%Lecture%#23% 10%Max%Delay%=% %Setup%Time%+%CLKNtoNQ%Delay%+%CL%Delay%Hint:%Frequency%=%1/Period%Pipelining%to%Improve%Performance%(1/2)%3/30/11% Fall%2010%NN%Lecture%#23% 11%Timing…%Extra%Register%are%olen%added%to%help%speed%up%the%clock%rate%Note:%delay%of%1%clock%cycle%from%input%to%output.%Clock%period%limited%by%propagaYon%delay%of%adder/shiler%Pipelining%to%Improve%Performance%(2/2)%3/30/11% Fall%2010%NN%Lecture%#23% 12%Timing…%• InserYon%of%register%allows%higher%clock%frequency%• More%outputs%per%second%Another%Great%Idea:%Finite%State%Machines%(FSM)%• You%may%have%seen%FSMs%in%other%classes%• Same%basic%idea%• FuncYon%can%be%represented%with%a%%“state%transiYon%diagram”%• With%combinaYonal%logic%and%registers,%any%FSM%can%be%implemented%in%hardware%3/30/11% Fall%2010%NN%Lecture%#23% 13%3/30/11%3%Example:%3%Ones%FSM%3/30/11% Fall%2010%NN%Lecture%#23% 14%Draw%the%FSM%…%FSM%to%detect%the%occurrence%of%3%consecuYve%1’s%in%the%Input%Assume%state%transiYons%are%controlled%by%%the%clock:%On%each%clock%cycle%the%machine%checks%the%inputs%and%moves%to%a%new%state%and%produces%a%new%output%…%=!Hardware%ImplementaYon%of%FSM%3/30/11% Fall%2010%NN%Lecture%#23% 15%+!Register%needed%to%hold%a%representaYon%of%the%machine’s%state.%Unique%bit%paGern%for%each%state.%CombinaYonal%logic%circuit%is%used%to%implement%a%funcYon%maps%from%present%state%and%input%to%next%state%and%output.%The%register%is%used%to%break%the%feedback%path%between%NS%and%PS,%controlled%by%the%clock%Hardware%for%FSM:%%CombinaYonal%Logic%3/30/11% Fall%2010%NN%Lecture%#23% 16%1"00"1"10"0"00"0"10"0"10"1"01"0"00"0"01"0"01"1"00"0"00"0"00"Output"NS"Input"PS"Truth%table%…%Can%look%at%its%funcYonal%specificaYon,%truth%table%form%Approximate%61C%Grade%So%Far%• ~½%points%for%full%course%• 25%%A,%50%%B,%15%%C,%10%%DNF%– GPA%=%2.85%– Fall%61C%2.81%• Extra%credit%moves%up%people%near%boarderline%(e.g.,%BN%to%B)%3/30/11% Spring%2011%NN%Lecture%#17% 17%Grades up to/including Lab 9Weighted raw score (as reported by glookup)Number of students300 350 400 450 5000 10 20 30 40 50Below C C B AAdministrivia%• Project%3,%Part%2%due%Sunday%4/3%– Thread%Level%Parallelism%and%OpenMP%• Last%homework%due%Sunday%4/10%• Project%4,%Part%1%due%Sunday%4/10;%Part%2%4/17%– Design%a%16Nbit%pipelined%computer%in%Logisim%– Labs%10%and%11%prepare%for%Project%4%• Lab%12%–%Malloc/Free%in%C%• Extra%Credit%due%4/24%–%Fastest%Matrix%MulYply%• Final%Exam%Monday%5/9%11:30N2:30PM%3/30/11% Spring%2011%NN%Lecture%#17% 18%Midway%Survey%Results%• Early%start%by%email%for%Fall%2011%61C?%– 70%%yes,%25%%maybe%• Read%textbook?%– 33%%before%lectures%– 50%%before%assignment%• AGend%lecture?%– 80%%rarely/never%miss%• Pace%of%lecture?%– 45%%liGle%fast,%30%%just%right,%10%%liGle%slow%• Enjoyed,%Learned%a%lot%– MapReduce%lab,%project%– MIPS%emulator%project%•
View Full Document