Introduction to Computer EngineeringChapter 1 Welcome AboardComputer System: Layers of AbstractionBig Idea #1: Universal Computing DeviceTuring MachineUniversal Turing MachineFrom Theory to PracticeBig Idea #2: Transformations Between LayersDeeper and Deeper…Descriptions of Each LevelDescriptions of Each Level (cont.)Many Choices at Each LevelWhat’s NextIntroduction to Computer EngineeringCS/ECE 252, Fall 2007Prof. Mark D. HillComputer Sciences DepartmentUniversity of Wisconsin – MadisonChapter 1Welcome AboardSlides based on set prepared by Gregory T. Byrd, North Carolina State University1-3Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Computer System: Layers of AbstractionSoftwareHardwareApplication ProgramLanguageInstruction Set Architecture (and I/O Interfaces) MicroarchitectureCircuitsDevicesAlgorithms1-4Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Big Idea #1: Universal Computing DeviceAll computers, given enough time and memory,are capable of computing exactly the same things.= =PDAWorkstationSupercomputer1-5Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Turing MachineMathematical model of a device that can performany computation – Alan Turing (1937)•ability to read/write symbols on an infinite “tape”•state transitions, based on current state and symbolEvery computation can be performed by some Turing machine. (Turing’s thesis)Tadda,b a+bTuring machine that addsTmula,b abTuring machine that multiplies1-6Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Universal Turing MachineTuring described a Turing machine that could implementall other Turing machines.•inputs: data, plus a description of computation (Turing machine)Ua,b,cc(a+b)Universal Turing MachineTadd, TmulU is programmable – so is a computer!•instructions are part of the input data•a computer can emulate a Universal Turing Machine, and vice versaTherefore, a computer is a universal computing device!1-7Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.From Theory to PracticeIn theory, computer can compute anything that’s possible to compute•given enough memory and timeIn practice, solving problems involves computing under constraints.•timeweather forecast, next frame of animation, ...•cost cell phone, automotive engine controller, ...•power cell phone, handheld video game, ...1-8Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Big Idea #2: Transformations Between LayersHow do we solve a problem using a computer?A systematic sequence of transformations between layers of abstraction.ProblemProblemAlgorithmAlgorithmProgramProgramSoftware Design:choose algorithms and data structuresProgramming:use language to express designInstr SetArchitectureInstr SetArchitectureCompiling/Interpreting:convert language to machine instructions1-9Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Deeper and Deeper…Instr SetArchitectureInstr SetArchitectureMicroarchMicroarchCircuitsCircuitsProcessor Design:choose structures to implement ISALogic/Circuit Design:gates and low-level circuits toimplement componentsDevicesDevicesProcess Engineering & Fabrication:develop and manufacturelowest-level components1-10Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Descriptions of Each LevelProblem Statement•stated using "natural language"•may be ambiguous, impreciseAlgorithm•step-by-step procedure, guaranteed to finish•definiteness, effective computability, finitenessProgram•express the algorithm using a computer language•high-level language, low-level languageInstruction Set Architecture (ISA)•specifies the set of instructions the computer can perform•data types, addressing mode1-11Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Descriptions of Each Level (cont.)Microarchitecture•detailed organization of a processor implementation•different implementations of a single ISALogic Circuits•combine basic operations to realize microarchitecture•many different ways to implement a single function (e.g., addition)Devices•properties of materials, manufacturability1-12Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Many Choices at Each LevelSolve a system of equationsGaussian eliminationJacobiiterationRed-black SOR MultigridFORTRAN C C++ JavaIntel x86Sun SPARC Compaq AlphaPentium II Pentium III AMD AthlonRipple-carry adder Carry-lookahead adderCMOS Bipolar GaAsTradeoffs:costperformancepower(etc.)1-13Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.What’s NextBits and Bytes•How do we represent information using electrical signals?Digital Logic•How do we build circuits to process information?Processor and Instruction Set•How do we build a processor out of logic elements?•What operations (instructions) will we implement?Assembly Language Programming•How do we use processor instructions to implement algorithms?•How do we write modular, reusable code? (subroutines)I/O, Traps, and Interrupts•How does processor communicate with outside