tailieunhanh - Lecture Introduction to computing systems (2/e): Chapter 1 - Yale N. Patt, Sanjay J. Patel

Chapter 1 - Welcome aboard. In this chapter, students will be able to understand three basic questions associated with computing systems: What are computing systems used for? How are computing systems implemented? What are computing systems able to do and how well can they do it? | Introduction to Computing Systems: From Bits and Gates to C and Beyond Yale N. Patt Sanjay J. Patel Slides prepared by Gregory T. Byrd, North Carolina State University 1- Chapter 1 Welcome Aboard Computer System: Layers of Abstraction Software Hardware Application Program Language Instruction Set Architecture (and I/O Interfaces) Microarchitecture Circuits Devices Algorithms 1- Big Idea #1: Universal Computing Device All computers, given enough time and memory, are capable of computing exactly the same things. = = PDA Workstation Supercomputer 1- Turing Machine Mathematical model of a device that can perform any computation – Alan Turing (1937) ability to read/write symbols on an infinite “tape” state transitions, based on current state and symbol Every computation can be performed by some Turing machine. (Turing’s thesis) Tadd a,b a+b Turing machine that adds Tmul a,b ab Turing machine that multiplies For more info about Turing machines, see 1- Universal Turing Machine Turing described a Turing machine that could implement all other Turing machines. inputs: data, plus a description of computation (Turing machine) U a,b,c c(a+b) Universal Turing Machine Tadd, Tmul U is programmable – so is a computer! instructions are part of the input data a computer can emulate a Universal Turing Machine, and vice versa Therefore, a computer is a universal computing device! 1- From Theory to Practice In theory, computer can compute anything that’s possible to compute given enough memory and time In 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- Big Idea #2: Transformations Between Layers How do we solve a problem using a computer? A systematic sequence of transformations between layers of abstraction. Problem Algorithm Program . | Introduction to Computing Systems: From Bits and Gates to C and Beyond Yale N. Patt Sanjay J. Patel Slides prepared by Gregory T. Byrd, North Carolina State University 1- Chapter 1 Welcome Aboard Computer System: Layers of Abstraction Software Hardware Application Program Language Instruction Set Architecture (and I/O Interfaces) Microarchitecture Circuits Devices Algorithms 1- Big Idea #1: Universal Computing Device All computers, given enough time and memory, are capable of computing exactly the same things. = = PDA Workstation Supercomputer 1- Turing Machine Mathematical model of a device that can perform any computation – Alan Turing (1937) ability to read/write symbols on an infinite “tape” state transitions, based on current state and symbol Every computation can be performed by some Turing machine. (Turing’s thesis) Tadd a,b a+b Turing machine that adds Tmul a,b ab Turing machine that multiplies For more info about Turing machines, see .