CS CoE EE 362 Digital Computers II Architecture Prof Mark Franklin jbf cse wustl edu Course Assistants Saurab Gayen Bryan 305I sg3 wustl edu Thursday 2 30 4 00 Eric Tyson Bryan 305J ejt1 cec wustl edu Tuesday 1 00 2 30 Required Book Heuring Jordan 2nd Edition Optional Book Intro VHDL Yalamanchili Handouts Academic Integrity Statement Course syllabus Grading elements Course Web Site http www cse wustl edu jbf cse362 d cse362 html Mark Franklin S07 CoE 362 Course Syllabus 1 Introduction Computer architecture What is it How do we define performance Simple performance models and metrics A general architecture taxonomy Underlying technologies trends implications Basic Architectures and a RISC processor Design of a Simple RISC Computer SRC Design of a single bus computer instruction set RTN Register Transfer Notation data path control Gate level design Assembly language programming VHDL module components Multiple bus architectures Mark Franklin S07 CoE 362 Course Syllabus 2 Improving Performance Pipelining and hazards Exploiting parallelism Instruction Level Parallelism ILP processor level parallelism CMP Chip MultiProcessor The Memory Hierarchy Memory organizations basic design Cache memory designs Virtual memory Overall system performance Other Topics Mass storage Disk systems Error detection and correction Computer arithmetic Running Topics VHDL Performance PROJECT Mark Franklin S07 Four Key Questions What components must every computer have How can computers be described specified evaluated What is performance how is it measured What constitutes computer architecture hardware software firmware algorithms etc How does technology effect computer architecture chip size feature size power pin density etc Mark Franklin S07 Essential Computer Components Processor interpret execute instructions Memory store instructions data Communication Device s communicate with outside world I O Processor Control Unit Classic Computer Architecture SISD Single Instruction Stream Single Data Stream Memory Input Output ALU Mark Franklin S07 Architecture Components INSTRUCTION SET DESIGN Programmer visible instruction set Algorithm compiler OS design algorithmic complexity ISA Instruction Set Architecture HIGH LEVEL COMPONENT ORGANIZATION Memory system bus structure processor design branch handling pipelining execution algorithms instructions second clocks instruction HARDWARE Detailed logic design packaging VLSI Logic design CAD algorithms speed area power OPERATING SYSTEM Scheduling of hardware resources e g virtual memory system threads processes system performance Mark Franklin S07 Program Control Unit Program Memory ALU ALU ALU ALU Interconnection Network Data Memory Unit Input Output SIMD Single Instruction Stream Multiple Data Stream Architecture Mark Franklin S07 Performance Expression Amdahl s Law f n fraction of operations that must be performed sequentially 0 f n 1 S maximum achieveable speedup 1 Tone processor S f n 1 f n p Tn processors p number of processors present E Efficiency S p Mark Franklin S07 Amdahl s Law It does no good to have many processors if there is not enough parallelism What portion of a computation can be sequential if we want the processors to be used at 50 percent efficiency S p 2 1 p 2 f n 1 f n p pf n 1 f n 2 1 fn p 1 i e To maintain a constant efficiency the fraction of the computation devoted to sequential processing must be proportional to the inverse of the number of processors Mark Franklin S07 Generalize Amdahl s Law 1 ExTimeold Speedupoverall ExTimene 1 Fractionenhanced Fractionenhanced w Speedupenhanced Example Suppose a program runs in 100 seconds on a machine Multiply operations are responsible for 80 seconds of this time a If multiplication could be done in zero time what speedup would be achieved b How much do we have to improve the speed of multiplication if we want the program to run 4 times faster What about 5 times faster PRINCIPAL Make the common case fast Mark Franklin S07 Computer Market Partitioning costs are for processor not system Desktop Computing 100 1 000 Price performance Servers 200 2 000 Availability reliability effectiveness Scalability Throughput Embedded Computers 0 20 1 000 Real time performance Power and memory minimization Cost minimization Interface with special purpose logic use of processor cores Mark Franklin S07 Architecture Taxonomy SISD Single Instruction Stream Single Data Stream SIMD Single Instruction Stream Multiple Data Stream MIMD Multiple Instruction Stream Multiple Data Stream MISD pipeline architecture Multiple Instruction Stream Single Data Stream Mark Franklin S07 HLL e g C C Perl vs Machine Assembly Language AL HLL Pros Easier to express algorithms due to higher level constructs e g For Case Arithmetic expressions objects etc Type checking Hardware for type checking Some memory allocation checking Assembly Language Pros More control over ISA more speed less memory More control over I O Combination is often best for embedded systems HLL calling AL Mark Franklin S07 Example HLL AL Mapping HLL b c d e AL LOAD R1 d LOAD R2 e LOAD R3 c MPY R4 R2 R1 ADD R5 R4 R3 STORE R5 b Mark Franklin S07 Buses I A set of path s wires connecting on chip or off chip modules Serial bus transmit one bit at a time Parallel bus transmits many bits simultaneously Generally time shared Generally has separate data control paths Typically has a separate bus controller or arbiter that decides which modules can use the bus at any given time Mark Franklin S07 Buses II Some common buses On chip AMBA Wishbone generally not standard Off chip PCI Bus Family 32bit transfer 64bit transfer 33 MHz PCI 133 MB sec 266 MB sec 66 MHz PCI 266 MB sec 532 MB sec 100 MHz PCI X 800 MB sec 133 MHz PCI X 1 GB sec PCI e xpress serial 1 lane 500 MB sec PCI e xpress serial 4 lanes 2 GB sec Off chip Other buses SCSI IDE Infiniband Common issues Arbitration congestion Logical equivalence between buses multiplexers and switches Mark Franklin S07 Bandwidth Requirements Mark Franklin S07 Bandwidth Trend Mark Franklin S07 Simple Queuing Theory View of Buses Bus is a shared resource and can be viewed as a server in a queuing system Modules attached to the bus present inputs i e requests to the server or Bus and are queued up if the server is busy Memory CPU I O Server 1 2 Queue 3 BUS Mark Franklin S07 Basic Queueing Theory Utilization time a server is busy Average Queue Length Avg of jobs in queue Average System Delay latency Avg time from job entry into to job departure from