Popular in Course
Popular in ComputerScienence
This 41 page Class Notes was uploaded by Sterling Schmeler on Monday October 26, 2015. The Class Notes belongs to CS1541 at University of Pittsburgh taught by SangyeunCho in Fall. Since its upload, it has received 59 views. For similar materials see /class/229379/cs1541-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.
Reviews for INTROTOCOMPUTERARCHITECTURE
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/26/15
CSCOE1541 Introduction to Computer Architecture Logic Desig n Review Sa ngyeu n Cho Dept of Computer Science University of Pittsburgh Logic design Digital hardware is implemented by way of logic design Digital circuits process and produce two discrete values 0 and 1 Example 1 bit full adder FA csCOEisM intro to ComputerArthitetture Umvermyufpirrsburgq Layered design approach Logic design is done using logic gates Often we desi39 n desired function usin39 hi h level Ianquot ua39es and somewhat higher level than logic gates Two approaches in design 0 Top down 0 Bottom up 5mm 3 a Tra nis isfo r s39 CSCOHSM lntro to Computer Architecture Universxcyufnnsburgh Transistor as a switch X X X G 61 30 Nquot type TR Y Y Y X X X G c 60 61 Pquot type TR Y Y Y CSCoElSM lntro to Computer Architecture Umve nyuf ttsburgq An inverter 1 Pquot type TR Y Nquot type TR 0 CSCOE1541 Who to Computer Arthwtenure Umvgrsnyufnnsburgq 1 Pquot type TR OFF A1 Y0 ON Nquot type TR 0 SCOHSM who to Computer Arthwtenure Umve nyuf ttsburgq WhenA 0 1 Pquot type TR ON Ao Y1 OFF Nquot type TR 0 CSCOE1541 ntro to Computer Arthwtenure Umvgrsnyufnnsburgq Abstra ctio n 1 Pquot type TR Y A Y Nquot type TR 0 SCOHSM who to Computer Arthwtenure Umve nyuf ttsburgq Logic gates 2input AND 2input OR 2input NAND 2input NOR CSCOHSM mm to Computer Arthwtenure gt w lt gt WW w lt w w gt lt YAampB YAB YA amp B YA B Unweme uf nasburgh Describing a function OutputA Fnput0 Input1 OutputB 39rm0 Input1 OutputC F nput0 Input1 Methods 0 Truth table 0 Sum of products 0 Product of sums CSCOHSM who to Computer Arthwtenure InputNi1 InputNi1 InputN71 Unweme uf nasburgh Truth table HHHDDDD JtJJJJJ CSC0E1541 Intro 0 Com pulev Avhiemve Umv my ofpmsburgh Sum of products HHHDDDD s A39B39cin A39BCin39 AB39Cin39 ABCin cout A39Bcin AB39cin ABCin39 ABCin CSC0E1541 Intro 0 Com pulev Avhiemve Umv my ofpmsburgh Combinational vs sequential logic Combinational logic function 0 Afunction whose out uts are de endent on on the current in uts 0 As soon as inputs are known outputs can be determined Sequential logic combinational logic memory 0 Some memory elements ie quotstatequot 0 Outputs are dependent on the current state and the current inputs 0 Next state is dependent on the current state and the current inputs CSCOHSM intro to Computer Arthitenure Unwermyufpmsbwh Com binatlonal logic inputs I I outputs CSCOHSM intro to Computer Arthitenure Unweme uf nasburgh Sequential logic inputs outputs clock CSCOHSM intro to Computer Arthitenure unwmnyufmsburgq Combinational logic Any combinational logic can be implemented using sum of I roducts or I roduct of sums Input output relationship can be defined in the truth table format From the truth table each output function can be derived Boolean expressions can be further manipulated eg to reduce cost using various Boolean algebraic rules SCOHSM intro to Computer Arthitenure Umve nyuf ttshurgq Boolean algebra Boole George 18151864 mathematician and hiloso her inventor of Boolean Al39ebra the basis of all computer arithmetic Binary values 01 Two binary operations AND gtlt OR One unary operation NOT CSCoElSM intro to Computer Architecture Universxcyufmsburgh Boolean algebra Binary operations AND gtlt OR o Idempotent aa aa a o Commutative ab ba ab ba o Associative abc abc abc abc o Distributive abc ab ac abc abac SCOHSM intro to Computer Architecture unmmyufmsburgq Boolean algebra De Morgan39s laws 0 ab ab o ab ab More 0 aaba o aaba aa aa 1 aa CSCOHSM intro to Computer Arthltenure umversnyufnnsburgh Expressive power With ANDORNOT we can express any function in Boolean algebra 0 Sum of products What is we have NANDNORNOT What if we have NAND only What if we have NOR only SCOHSM intro to Computer Arthltenure Umve nyuf nshurgq Multiplexor aka MUX A Y B s v s 7 B A wcomsm m ucmpmmmW ammmmmmh A 32 bit MUX 521m 5mm AQA 39 W C B 32 M u an 58 quot a agzwwmnnmlmme w u rmAlwmwnummumbaclwumnumy my m mumnmm Moms who mampmerAmMadwe amwmcyommmh Simplifying expressions cout A39Bcin AB39Cin ABCin39 ABCin cout BCin Acin AB CSCOHSM intro to Computer Arthitenure Universityuf nsbur 1 Karnaugh map ch 0 1 AC In BC in AB C BCinABACin out SCOHSM intro to Computer Arthitenure Umve nyuf ttsburgq Building a 1bit ALU ALU arithmetic logic unit arithmetic unit logic unit rummw mein Operation 3 D Resu it CSCu SM mm m CamputsrArzhitscmre Umvemlyumesburgq rm m cmmn mm m v 2mm I ALUZ I gt Home A cirva i v m i Camin m Mum ermx CsCumsm mm m CamputsrArzhitscmre Umvemw pmmgh Implementing quotsubquot Bin 9 Opermion Carryln V Carryout CSC0E1541 who to Computer Arcmtedure Unwmny ofpmsburgh Implementing NAND and NOR A39mverl Operamn Binven Carryln CarryOm CSC0E1541 mm to Computer Arcmtedure Unwmny ofpmsburgh Implementing SLT setlessthan 1 biALU for bits o 30 1 bit ALU for bit 31 Mann Mro mmwewmmre Umvzmtynfhmhuxgh Implementing SLT setlessthan Moms who mampmerAmMadwe Umvzmtynfhmhuxgh Supporting BEQ and BNE Mum l 11mm A 7 w umm H m L 39 t quotzero detectorquot emu DDW V mam CSCOHSM mm to ComputerAnhnenure Umversxty uf qusburgh Abstracting ALU ALU operation a Zero Result Over ow b 4 Canyom Note that ALU is a combinational logic CSCOHSM who to ComputerAnhnenure Umvermyufpmsburgq RS latch R Q G S Beware of the feedback 51mm m We 0 mmmmm quotWNWMW RS latch lS When R0 51 ytumsm Mm m ompummmm Umvemtyofhnsbuxgh RS latch 08 When R1 50 ytumsm Mm m ompummmm Umvemtyofhnsbuxgh RS latch When R0 50 and Q was 0 ytumsm Mm m ompummmm Umvemtyofhnsbuxgh RS latch When R0 50 and Q was1 ytumsm Mm m ompummmm Umvemtyofhnsbuxgh RS latch 0 18 What happens if RS1 ytumsm Mm m ompummmm Umvemtyofhnsbuxgh D latch Note that we have an RS latch in the backend of this design mam mm m ompummmm Umvemtym39hnsbuxgh D latch Note that R S inputs always get opposite values when C1 When C0 SR0 2 RS latch remembers the previous value mam mm m ompummmm Umwmmmmmg D latch quotlatched modequot quottransparent modequot CSCOE1541 ntro to computa Arcmtecmre Unwemty of thtsburgh D latch D Latch C I Q CSCOE1541 ntro to computa Arcmtecmre Unwemty of thtsburgh 21 D flipflop DFF Two cascaded D latches C input of the second is inverted This is a negative edge triggered DFF SComsm mm m CamputsrArzhitscmre Umvemryurpmmgq D flipflop SComsm mm m CamputsrArzhitscmre Umvemiyurpmmgq 22 Finite state machine FSM L Next state Nextstale iunclion Current state Output iunclion 4 ou pms CSCoEi 541 intro to Computer Architecture Umv my ofPMsburgq Traffic light control example Two states 0 NSlite reen iht on NorthSouth road 0 EWIite green light on EastWest road Current state goes for 30 seconds then 0 Switch to the other state if there is a car waiting 0 Current state goes for another 30 seconds if not We use 130 Hz clock CSCoEi 541 intro to Computer Architecture Umv my ofPMsburgq 23 Traffic light control example cm mm mm 1 0 ngmen l Ewgree n l 1 CSCoEl 541 intro to Computer Architedure Unwas y ofPMsburgh Traffic light control example EWcar EWgreen NScar CSCoEl 541 intro to Computer Architecture Unwas ty ofPtLsturgh 24 Traffic light control example Let39s assign quotOquot to NSIite and quot1quot to EWIite initially NextState CurrentState39EWcar CurrentStateNScar NSIite CurrentState39 EWIite CurrentState cscwsm intro to Computer Architecture Un ve nyuf nsburgq To wrap up In digital logic transistors are used as simple switches Logic gates are an abstraction of a transistor network A combinational logic block has inputs and outputs whose values are immediately determined as inputs become known A sequential logic block is composed of a combinational logic block and memory elements SCOHSM intro to Computer Architecture Umve nyuf nsburgq 25 To wrap up Boolean algebra provides a theoretical foundation for digital logic Starting from two transistors N type and P type we39ve built logic gates and more complex structures bottom up An ALU for the MIPS architecture has been built CSCoElSM intro to Computer Architecture unwmnyufmsburgq To wrap up Flip flops FFs were used as a memory element A finite state machine FSM can be implemented using FFs and some combinational logic CSCoElSM intro to Computer Architecture Umve nyuf ttshurgq 26 CSCOE1541 Introduction to Com puter Architecm re Logic Design Review Sangyeun cm as a campmarsciam Weary a Pnlshufgh Layered design approach Logic design is done using iogic gates Often we design desired function using highrievei ianguages mewhat higha ievei than iogic gates and so Two approaches in design Top down ammo Logic design Digitai hardware is impiawmted by way or logic design Digitai Circuits process and produce two discrete vaiues o and i Exampie 17bit mii aooe FA new M as mm imam Transistor as a switch x x x e 6 eeu w mam v v DEW V V An inverter pHype n2 WhenA 0 pwtype n2 A v H OFF D W m WWW W m WWW When A 1 Abstraction 1 1 P Hype m WW2 TR OFF M A v A Do v D W m WWW W m WWW Logic gates Jgt 24mm AND 1gt v YA amp B a A 24mm OR v Y2 B a 24mm NAND A1gtov vmw amp B a A 24mm NOR v YNAi B 3 Moms m mmmmime ammurmmh Truth table ccnmsm intro mmpmawmedm Umvexsnym39Pmsbuxdl Describing a function OutputA FInput0 Inputw Inputw OutputB F39Input0 Inputw Inputw OutputC FquotInput0 Inputw Inputw Methods Truth table Sum of products Product of sums Gcumsm imm ocumpmaAmmmure Umvusxtyufpmsbmgh Sum of products s A39B39Cm A39ch39 AB39cm39 Ach cout A39ch AB39cm Ach39 Ach ccnmsm intro mampmaArmmedure Umvexsnym39Pmsbuxdl Combinational vs sequential logic Combinational logic function A function whose outputs are dependent only on the current inputs As soon as inputs are known outputs an be determined Se uential loic combinational loic memor ome memory elements ie quotstatequot Outputs are dependent on the current state and the current inputs Next state is dependent on the current state and the current inputs zyzr sm m mzmvmeimznnmme Sequential logic inputs quotmm mm z mm m mzmvmsmznnmme Wm mm Combinational logic Combinational logic Any combinational logic can be implemented using sum of products or product of sums Inputoutput relationship can be defined in the truth table format inputs WINS From the truth table each output function can be derived Boolean expressions can be further manipulated eg to reduce cost using various Boolean algebraic rules gzu sm m mmpnummue quotmm mm z mm m mmpneuenmue thvexsllyuf assuage Boolean algebra Boole George 18151864 mathematician and philosopher inventor of Boolean Algebra the basis of all computer arithmetic Binary values 01y Two binary operations AND X OR One unaly operation NO zyzumsm m tozmvmeimznnmme Boolean algebra De Morgan39s laws ab a b ab ab quotmm mm z mm m rozmvmsmznnmme Wm mm Boolean algebra Expressive power Binary operations AND X OR With ANDORNOT We can express any function in Boolean Idempotent al ebra aaaaa Sumofproducts Commutative b b 5 is What is We have NANDNORNOT Associative What if We have NAND only a b C a b C What if We have NOR only a abc Distributive tam abac ab c ab ac gzu sm m mmmtmmmm Wm mm z mm m mmmmmmm thvexs yvf mum Multiplexer aka MUX vs 7 mm M mm mm Simplifying expressions cum 39Ecm Aa39cm Aacm39 Aacm cum 5cm ACm AE A 32bit MUX mm M mm mm Karnaugh map Building a 1bit ALU ALU arithmetic logic Lmlt arithmetic mm logic Lmlt Implementing quotsubquot Building a 32bit ALU Implementing NAND and NOR Implementing SLT setIessthan tunmumrmsmzu mmuwm 2 mm M mm uw mu Supporting BEQ and BNE Implementing SLT setIessthan Abstracting ALU Note that ALU s a ombmamona ogK RS latch RS latch R 1 R Q C S 0 S Beware of the feedback When R1 50 mam m m MWMWMW ammmmmzh c mew We a omvkatMedwe ammwmm RS latch RS latch 0 R l S When R0 51 When R0 50 and Q was 0 mam m m MWMWMW ammmmmzh c mew We a omvkatMedwe ammwmm RS latch D latch C Q 5 D When R0 50 and Q was1 Note that we have an RS latch in the backend of this design sumsoi m m mumman Umvemlyufhnsbmgh mam We in MWMMW quotmmwmw RS latch D latch 1 R Q C l S Note that R S inputs always get opposite values when 21 When 20 SR0 2 RS latch remembers the previous What happens If RS1 value SDE15M mm m ompummmnm Umvemlyofhnsbmgh lt mum lmru m ompmerktmledwe quotmmmmmm D latch quottransparent mode SDE15M intro mmwmmmnm D flipflop DFF Two cascaded D latches C input of the second is inverted This is a negative edge triggered DFF D latch D flipflop 390 D Q I I D Q B I I I I I I C u n c i i w w Finite state machine FSM MW Traffic light control example Traffic light control example Twostates NShte green hemquot Nenhsem road Ewhte green hemquot EastrWesnuad Current state goes for 30 seconds then Sinitletotheothermmxfthereisazarwamng Current state goes for another 30 seems if not We use 130 Hz lock Traffic light control example m y use mikequot Nsmv l Wm N5 Traffic light control example Let39s assign quot0quot to NSlite and quot1quot to EWlite initially z E m l n E E E K E m EWlite CurrentState yam m m mzmvmevmznnmme Uriquotsnufme To wrap up Boolean algebra provides a theoretical foundation for digital logic Starting from two transistors Ntype and Ptype we39ve built logic gates and more complex structures bottom up An ALU forthe MIPS architecture has been built z Kmsm m rozmvmsmznnmme thvusixyvfhmmngn To wrap up In digital logic transistors are used as simple switches Logic gates are an abstraction of a transistor network A combinational logic block has inputs and outputs whose values are immediately determined as inputs become known A sequential logic blockis composed ofa combinational logic block and memory elements yam m m mzmvmevmznnmme Uriquotsnufme To wrap up Flipflops FFs were used as a memory element A finite state machine FSM can be implemented using FFs and some combinational logic z Kmsm m rozmvmsmznnmme thvusixyvfhmmngn CSCoE 1541 Final exam review sheet 4152009 Multiprocessor MP Can you explain why MP helps improve the performance of different workloads eg scientific application server application PC environment What is MP cache coherence What is the difference between writeupdate and writeinvalidate policy What is memory consistency model How is it related to cache coherence protocol What is sequential consistency model and why does it pose challenges for hardware designers Can you reason about the memory access interleaving from different programs running simultaneously Can you explain the difference between the shared memory programming model and the message passing programming model Can you calculate how long it takes for a network packet to travel from a source node to a destination node given the baseline latency bandwidth and the routing method used What are memorymapped lO and dedicated lO address space What is DMA and how does it help improve system performance What are the components of hard disk access time How can we improve reduce each component Can you explain the difference between interrupt and polling mechanism Can you explain about potential cache coherence problems caused by lO operations and how to prevent them What are different types of bus signals and what are they for lll Miscellany Time equation TIME IC x CPI x CCT is important Make sure you know how to compare two designs in terms of performance ie A is faster than B by X Good luck
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'