Lecture notes on Parallel Computing

Evolution of Computer Systems & Trends towards Parallel Processing and how are parallel processing system are classified pdf free download
ImogenCameron Profile Pic
ImogenCameron,France,Teacher
Published Date:14-07-2017
Your Website URL(Optional)
Comment
1 UNIT – 1 Lesson 1: Evolution of Computer Systems & Trends towards parallel Processing Contents: 1.0 Aims and Objectives 1.1 Introduction 1.2 Introduction to Parallel Processing 1.2.1 Evolution of Computer Systems 1.2.2 Generation of Computer Systems 1.2.3 Trends towards Parallel Processing 1.3 Let us Sum Up 1.4 Lesson-end Activities 1.5 Points for Discussions 1.6 References 1.0 Aims and Objectives The main aim of this lesson is to learn the evolution of computer systems in detail and various trends towards parallel processing. 1.1 Introduction Over the past four decades the computer industry has experienced four generations of development. The first generation used Vacuum Tubes (1940 – 1950s) to discrete diodes to transistors (1950 – 1960s), to small and medium scale integrated circuits (1960 – 1970s) and to very large scale integrated devices (1970s and beyond). Increases in device speed and reliability and reduction in hardware cost and physical size have greatly enhanced computer performance. The relationships between data, information, knowledge and intelligence are demonstrated. Parallel processing demands concurrent execution of many programs in a computer. The highest level of parallel processing is conducted among multiple jobs through multiprogramming, time sharing and multiprocessing 1.2 Introduction to Parallel Processing Basic concepts of parallel processing on high-performance computers are introduced in this unit. Parallel computer structures will be characterized as Pipelined computers, array processors and multiprocessor systems. 1.2.1 Evolution of Computer Systems Over the past four decades the computer industry has experienced four generations of development. 1.2.2 Generations Of Computer Systems First Generation (1939-1954) - Vacuum Tube  1937 - John V. Atanasoff designed the first digital electronic computer.  1939 - Atanasoff and Clifford Berry demonstrate in Nov. the ABC prototype. 2  1941 - Konrad Zuse in Germany developed in secret the Z3.  1943 - In Britain, the Colossus was designed in secret at Bletchley Park to decode German messages.  1944 - Howard Aiken developed the Harvard Mark I mechanical computer for the Navy.  1945 - John W. Mauchly and J. Presper Eckert built ENIAC(Electronic Numerical Integrator and Computer) at U of PA for the U.S. Army.  1946 - Mauchly and Eckert start Electronic Control Co., received grant from National Bureau of Standards to build a ENIAC-type computer with magnetic tape input/output, renamed UNIVAC( in 1947 but run out of money, formed in Dec. 1947 the new company Eckert-Mauchly Computer Corporation (EMCC).  1948 - Howard Aiken developed the Harvard Mark III electronic computer with 5000 tubes  1948 - U of Manchester in Britain developed the SSEM Baby electronic computer with CRT memory  1949 - Mauchly and Eckert in March successfully tested the BINAC stored-program computer for Northrop Aircraft, with mercury delay line memory and a primitive magentic tape drive; Remington Rand bought EMCC Feb. 1950 and provided funds to finish UNIVAC  1950- Commander William C. Norris led Engineering Research Associates to develop the Atlas, based on the secret code-breaking computers used by the Navy in WWII; the Atlas was 38 feet long, 20 feet wide, and used 2700 vacuum tubes  In 1950, the first stored program computer,EDVAC(Electronic Discrete Variable Automatic Computer), was developed.  1954 - The SAGE aircraft-warning system was the largest vacuum tube computer system ever built. It began in 1954 at MIT's Lincoln Lab with funding from the Air Force. The first of 23 Direction Centers went online in Nov. 1956, and the last in 1962. Each Center had two 55,000-tube computers built by IBM, MIT, AND Bell Labs. The 275-ton computers known as "Clyde" were based on Jay Forrester's Whirlwind I and had magnetic core memory, magnetic drum and magnetic tape storage. The Centers were connected by an early network, and pioneered development of the modem and graphics display. Second Generation Computers (1954 -1959) – Transistor  1950 - National Bureau of Standards (NBS) introduced its Standards Eastern Automatic Computer (SEAC) with 10,000 newly developed germanium diodes in its logic circuits, and the first magnetic disk drive designed by Jacob Rabinow  1953 - Tom Watson, Jr., led IBM to introduce the model 604 computer, its first with transistors, that became the basis of the model 608 of 1957, the first solid-state computer for the commercial market. Transistors were expensive at first.  TRADIC(Transistorized digital Computer), was built by Bell Laboratories in 1954.  1959 - General Electric Corporation delivered its Electronic Recording Machine Accounting (ERMA) computing system to the Bank of America in California; based on a design by SRI, the ERMA system employed Magnetic Ink Character Recognition (MICR) as the means to capture data from the checks and introduced automation in banking that continued with ATM machines in 1974. 3  The first IBM scientific ,transistorized computer, IBM 1620, became available in 1960. Third Generation Computers (1959 -1971) - IC  1959 - Jack Kilby of Texas Instruments patented the first integrated circuit in Feb. 1959; Kilby had made his first germanium IC in Oct. 1958; Robert Noyce at Fairchild used planar process to make connections of components within a silicon IC in early 1959; the first commercial product using IC was the hearing aid in Dec. 1963; General Instrument made LSI chip (100+ components) for Hammond organs 1968.  1964 - IBM produced SABRE, the first airline reservation tracking system for American Airlines; IBM announced the System/360 all-purpose computer, using 8-bit character word length (a "byte") that was pioneered in the 7030 of April 1961 that grew out of the AF contract of Oct. 1958 following Sputnik to develop transistor computers for BMEWS.  1968 - DEC introduced the first "mini-computer", the PDP-8, named after the mini-skirt; DEC was founded in 1957 by Kenneth H. Olsen who came for the SAGE project at MIT and began sales of the PDP-1 in 1960.  1969 - Development began on ARPAnet, funded by the DOD.  1971 - Intel produced large scale integrated (LSI) circuits that were used in the digital delay line, the first digital audio device. Fourth Generation (1971-1991) - microprocessor  1971 - Gilbert Hyatt at Micro Computer Co. patented the microprocessor; Ted Hoff at Intel in February introduced the 4-bit 4004, a VSLI of 2300 components, for the Japanese company Busicom to create a single chip for a calculator; IBM introduced the first 8-inch "memory disk", as it was called then, or the "floppy disk" later; Hoffmann-La Roche patented the passive LCD display for calculators and watches; in November Intel announced the first microcomputer, the MCS-4; Nolan Bushnell designed the first commercial arcade video game "Computer Space"  1972 - Intel made the 8-bit 8008 and 8080 microprocessors; Gary Kildall wrote his Control Program/Microprocessor (CP/M) disk operating system to provide instructions for floppy disk drives to work with the 8080 processor. He offered it to Intel, but was turned down, so he sold it on his own, and soon CP/M was the standard operating system for 8-bit microcomputers; Bushnell created Atari and introduced the successful "Pong" game  1973 - IBM developed the first true sealed hard disk drive, called the "Winchester" after the rifle company, using two 30 Mb platters; Robert Metcalfe at Xerox PARC created Ethernet as the basis for a local area network, and later founded 3COM  1974 - Xerox developed the Alto workstation at PARC, with a monitor, a graphical user interface, a mouse, and an ethernet card for networking  1975 - the Altair personal computer is sold in kit form, and influenced Steve Jobs and Steve Wozniak  1976 - Jobs and Wozniak developed the Apple personal computer; Alan Shugart introduced the 5.25-inch floppy disk  1977 - Nintendo in Japan began to make computer games that stored the data on chips inside a game cartridge that sold for around 40 but only cost a few dollars to manufacture. It introduced its most popular game "Donkey Kong" in 1981, Super Mario Bros in 1985 4  1978 - Visicalc spreadsheet software was written by Daniel Bricklin and Bob Frankston  1979 - Micropro released Wordstar that set the standard for word processing software  1980 - IBM signed a contract with the Microsoft Co. of Bill Gates and Paul Allen and Steve Ballmer to supply an operating system for IBM's new PC model. Microsoft paid 25,000 to Seattle Computer for the rights to QDOS that became Microsoft DOS, and Microsoft began its climb to become the dominant computer company in the world.  1984 - Apple Computer introduced the Macintosh personal computer January 24.  1987 - Bill Atkinson of Apple Computers created a software program called HyperCard that was bundled free with all Macintosh computers. Fifth Generation (1991 and Beyond)  1991 - World-Wide Web (WWW) was developed by Tim Berners-Lee and released by CERN.  1993 - The first Web browser called Mosaic was created by student Marc Andreesen and programmer Eric Bina at NCSA in the first 3 months of 1993. The beta version 0.5 of X Mosaic for UNIX was released Jan. 23 1993 and was instant success. The PC and Mac versions of Mosaic followed quickly in 1993. Mosaic was the first software to interpret a new IMG tag, and to display graphics along with text. Berners-Lee objected to the IMG tag, considered it frivolous, but image display became one of the most used features of the Web. The Web grew fast because the infrastructure was already in place: the Internet, desktop PC, home modems connected to online services such as AOL and CompuServe.  1994 - Netscape Navigator 1.0 was released Dec. 1994, and was given away free, soon gaining 75% of world browser market.  1996 - Microsoft failed to recognize the importance of the Web, but finally released the much improved browser Explorer 3.0 in the summer. 1.2.3 Trends towards Parallel Processing From an application point of view, the mainstream of usage of computer is experiencing a trend of four ascending levels of sophistication:  Data processing  Information processing  Knowledge processing  Intelligence processing Computer usage started with data processing, while is still a major task of today’s computers. With more and more data structures developed, many users are shifting to computer roles from pure data processing to information processing. A high degree of parallelism has been found at these levels. As the accumulated knowledge bases expanded rapidly in recent years, there grew a strong demand to use computers for knowledge processing. Intelligence is very difficult to create; its processing even more so. Todays computers are very fast and obedient and have many reliable memory cells to be qualified for data-information-knowledge processing. Computers are far from being satisfactory in performing theorem proving, logical inference and creative thinking. 5 From an operating point of view, computer systems have improved chronologically in four phases:  batch processing  multiprogramming  time sharing  multiprocessing Intelligence Processing Knowledge Processing Increasing Complexity Increasing Volumes and Sophistication in of raw material to be Processing processed Information Processing Data Processing Figure 1.1 The spaces of data, information, knowledge and intelligence from the viewpoint of computer processing In these four operating modes, the degree of parallelism increase sharply from phase to phase. We define parallel processing as Parallel processing is an efficient form of information processing which emphasizes the exploitation of concurrent events in the computing process. Concurrency implies parallelism, simultaneity, and pipelining. Parallel processing demands concurrent executiom of many programs in the computer. The highest level of parallel processing is conducted among multiple jobs or programs through multiprogramming, time sharing, and multiprocessing. Parallel processing can be challenged in four programmatic levels:  Job or program level  Task or procedure level  Interinstruction level  Intrainstruction level The highest job level is often conducted algorithmically. The lowest intra-instruction level is often implemented directly by hardware means. Hardware roles increase from high to low levels. On the other hand, software implementations increase from low to high levels. 6 Console CPU Floppy R PC Disk 0 Main Memory . 32 2 Words of 32 ALU . bits each . Registers Local Memory Synchronous back plane interconnect (SBI) Unibus Massbus MassBus Uni Bus Adapter Adapter I/O Devices I/O Devices SBI I/O Device Input – Output Sub System Figure 1.2 The system architecture of the super mini VAX – 11/780 microprocessor system The trend is also supported by the increasing demand for a faster real-time, resource sharing and fault-tolerant computing environment. Diagnostic Memory Floating – Point Accelerator 7 It requires a broad knowledge of and experience with all aspects of algorithms, languages, software, hardware, performance evaluation and computing alternatives. To achieve parallel processing requires the development of more capable and cost effective computer system. 1.3 Let us Sum Up With respect to parallel processing, the general architecture trend is being shifted from conventional uniprocessor systems to multiprocessor systems to an array of processing elements controlled by one uniprocessor. From the operating system point of view computer systems have been improved to batch processing, multiprogramming, and time sharing and multiprocessing. Computers to be used in the 1990 may be the next generation and very large scale integrated chips will be used with high density modular design. More than 1000 mega float point operation per second are expected in these future supercomputers. The evolution of computer systems helps in learning the generations of computer systems. 1.4 Lesson-end Activities 1. Discuss the evolution and various generations of computer systems. 2. Discuss the trends in mainstream computer usage. 1.5 Points for Discussions  The first generation used Vacuum Tubes (1940 – 1950s) to discrete diodes to transistors (1950 – 1960s), to small and medium scale integrated circuits (1960 – 1970s) and to very large scale integrated devices (1970s and beyond). 1.6 References 1. Advanced Computer Architecture and Parallel Processing by Hesham El-Rewini M. Abd-El- Barr Copyright © 2005 by John Wiley & Sons, Inc. 2. www.cs.indiana.edu/classes 8 Lesson 2 : Parallelism in Uniprocessor Systems Contents: 2.0 Aims and Objectives 2.1 Introduction 2.2 Parallelism in Uniprocessor Systems 2.2.1 Basic Uniprocessor Architecture 2.2.2 Parallel Processing Mechanisms 2.3 Let us Sum Up 2.4 Lesson-end Activities 2.5 Points for discussions 2.6 References 2.0 Aims and Objectives The main aim of this lesson is to know the architectural concepts of Uniprocessor systems. The development of Uniprocessor system will be introduced categorically. 2.1 Introduction The typical Uniprocessor system consists of three major components: the main memory, the Central processing unit (CPU) and the Input-output (I/O) sub-system. The CPU contains an arithmetic and logic unit (ALU) with an optional floating-point accelerator, and some local cache memory with an optional diagnostic memory. The CPU, the main memory and the I/O subsystems are all connected to a common bus, the synchronous backplane interconnect (SBI) through this bus, all I/O device scan communicate with each other, with the CPU, or with the memory. A number of parallel processing mechanisms have been developed in uniprocessor computers and they are identified as multiplicity of functional units, parallelism and pipelining within the CPU, overlapped CPU and I/O operations, use of a hierarchical memory system, multiprogramming and time sharing, multiplicity of functional units. 2.2 Parallelism in Uniprocessor Systems A typical uniprocessor computer consists of three major components: the main memory, the central processing unit (CPU), and the input-output (I/O) subsystem. The architectures of two commercially available uniprocessor computers are given below to show the possible interconnection of structures among the three subsystems. There are sixteen 32-bit general purpose registers, one of which serves as the program Counter (pc).there is also a special CPU status register containing information about the current state of the processor and of the program being executed. The CPU contains an arithmetic and logic unit (ALU) with an optional floating-point accelerator, and some local cache memory with an optional diagnostic memory. 9 2.2.1 Basic Uniprocessor Architecture The CPU, the main memory and the I/O subsystems are all connected to a common bus, the synchronous backplane interconnect (SBI) through this bus, all I/O device scan communicate with each other, with the CPU, or with the memory. Peripheral storage or I/O devices can be connected directly to the SBI through the unibus and its controller or through a mass bus and its controller. LOGICAL STORAGE UNITS LSU0 LSU1 LSU2 LSU3 STORAGE CONTROLLER Central Processing Unit (CPU) I/O CHANNELS I/O Sub System Figure 2.1 The System Architecture of the mainframe IBM System The CPU contains the instruction decoding and execution units as well as a cache. Main memory is divided into four units, referred to as logical storage units that are four-way interleaved. The storage controller provides mutltiport connections between the CPU and the four LSUs. Peripherals are connected to the system via high speed I/O channels which operate asynchronously with the CPU. 10 2.2.2 Parallel Processing Mechanism A number of parallel processing mechanisms have been developed in uniprocessor computers. We identify them in the following six categories:  multiplicity of functional units  parallelism and pipelining within the CPU  overlapped CPU and I/O operations  use of a hierarchical memory system  multiprogramming and time sharing  multiplicity of functional units Multiplicity of Functional Units The early computer has only one ALU in its CPU and hence performing a long sequence of ALU instructions takes more amount of time. The CDC-6600 has 10 functional units built into its CPU. These 10 units are independent of each other and may operate simultaneously. A score board is used to keep track of the availability of the functional units and registers being demanded. With 10 functional units and 24 registers available, the instruction issue rate can be significantly increased. Another good example of a multifunction uniprocessor is the IBM 360/91 which has 2 parallel execution units. One for fixed point arithmetic and the other for floating point arithmetic. Within the floating point E-unit are two functional units:one for floating point add- subtract and other for floating point multiply – divide. IBM 360/91 is a highly pipelined, multifunction scientific uniprocessor. Parallelism And Pipelining Within The Cpu Parallel adders, using such techniques as carry-look ahead and carry –save, are now built into almost all ALUs. This is in contrast to the bit serial adders used in the first generation machines. High speed multiplier recording and convergence division are techniques for exploring parallelism and the sharing of hardware resources for the functions of multiply and divide. The use of multiple functional units is a form of parallelism with the CPU. Various phases of instructions executions are now pipelined, including instruction fetch,decode,operand fetch, arithmetic logic execution, and store result. Overlapped CPU and I/O Operations I/O operations can be performed simultaneously with the CPU competitions by using separate I/O controllers, channels, or I/O processors. The direct memory access (DMA) channel can be used to provide direct information transfer between the I/O devices and the main memory. The DMA is conducted on a cycle stealing basis, which is apparent to the CPU. Use of Hierarchical Memory System 11 The CPU is 1000 times faster than memory access. A hierarchical memory system can be used to close up the speed gap. The hierarchical order listed is  registers  Cache  Main Memory  Magnetic Disk  Magnetic Tape The inner most level is the register files directly addressable by ALU. Cache memory can be used to serve as a buffer between the CPU and the main memory. Virtual memory space can be established with the use of disks and tapes at the outer levels. Balancing Of Subsystem Bandwidth CPU is the fastest unit in computer. The bandwidth of a system is defined as the number of operations performed per unit time. In case of main memory the memory bandwidth is measured by the number of words that can be accessed per unit time. Bandwidth Balancing Between CPU and Memory The speed gap between the CPU and the main memory can be closed up by using fast cache memory between them. A block of memory words is moved from the main memory into the cache so that immediate instructions can be available most of the time from the cache. Bandwidth Balancing Between Memory and I/O Devices Input-output channels with different speeds can be used between the slow I/O devices and the main memory. The I/O channels perform buffering and multiplexing functions to transfer the data from multiple disks into the main memory by stealing cycles from the CPU. Multiprogramming Within the same interval of time, there may be multiple processes active in a computer, competing for memory, I/O and CPU resources. Some computers are I/O bound and some are CPU bound. Various types of programs are mixed up to balance bandwidths among functional units. Example Whenever a process P1 is tied up with I/O processor for performing input output operation at the same moment CPU can be tied up with an process P2. This allows simultaneous execution of programs. The interleaving of CPU and I/O operations among several programs is called as Multiprogramming. Time-Sharing The mainframes of the batch era were firmly established by the late 1960s when advances in semiconductor technology made the solid-state memory and integrated circuit feasible. These 12 advances in hardware technology spawned the minicomputer era. They were small, fast, and inexpensive enough to be spread throughout the company at the divisional level. Multiprogramming mainly deals with sharing of many programs by the CPU. Sometimes high priority programs may occupy the CPU for long time and other programs are put up in queue. This problem can be overcome by a concept called as Time sharing in which every process is allotted a time slice of CPU time and thereafter after its respective time slice is over CPU is allotted to the next program if the process is not completed it will be in queue waiting for the second chance to receive the CPU time. 2.3 Let us Sum Up The architectural design of Uniprocessor systems has been discussed with the help of 2 examples system architecture of the supermini VAX-11/780 Uniprocessor system. And System Architecture of the mainframe IBM system 370/Model 168 Uniprocessor computer. Various components such as main memory, Unibus Adapter, mass Bus adapter SBI I/O device have been discussed. A number of parallel processing mechanisms have been developed in Uniprocessor computers and the categorization made to understand various parallelism. 2.4 Lesson-end Activities 1. Illustrate how parallelism can be implemented in uniprocessor architecture. 2. How system bandwidth can be balanced? Discuss. 2.5 Points for Discussions The CPU, the main memory and the I/O subsystems are all connected to a common bus, the synchronous backplane interconnect (SBI) through this bus, all I/O device scan communicate with each other, with the CPU, or with the memory. Peripheral storage or I/O devices can be connected directly to the SBI through the unibus and its controller or through a mass bus and its controller. The hierarchical order of memory systems are listed  registers  Cache  Main Memory  Magnetic Disk  Magnetic Tape Band Width: The bandwidth of a system is defined as the number of operations performed per unit time. The interleaving of CPU and I/O operations among several programs is called as Multiprogramming. Time sharing is mechanism in which every process is allotted a time slice of CPU time and thereafter after its respective time slice is over CPU is allotted to the next program if the process is not completed it will be in queue waiting for the second chance to receive the CPU time. 13 2.6 References  Parallel Processing Computers – Hayes  Computer Architecture and Parallel Processing – Kai Hwang  Operating Systems - Donovan 14 Lesson 3: Parallel Computer Structures Contents: 3.0 Aims and Objectives 3.1 Introduction 3.2 Parallel Computer Structures 3.2.1 Pipeline Computers 3.2.2 Array Processors 3.2.3 Multiprocessor Systems 3.3 Let us Sum Up 3.4 Lesson-end Activities 3.5 Points for discussions 3.6 References 3 Aims and Objectives The main objective of this lesson is to learn the parallel computers three architectural configurations called pipelined computers, Array Processors, and Multiprocessor Systems. 3.1 Introduction Parallel computers are those systems that emphasize parallel processing. The process of executing an instruction in a digital computer involves 4 major steps namely Instruction fetch, Instruction decoding, Operand fetch, Execution. In a pipelined computer successive instructions are executed in an overlapped fashion. In a non pipelined computer these four steps must be completed before the next instructions can be issued. An array processor is a synchronous parallel computer with multiple arithmetic logic units called processing elements (PE) that can operate in parallel in lock step fashion. By replication one can achieve spatial parallelism. The PEs are synchronized to perform the same function at the same time. A basic multiprocessor contains two or more processors of comparable capabilities. All processors share access to common sets of memory modules, I/O channels and peripheral devices. 3.2 Parallel Computer Structures Parallel computers are those systems that emphasize parallel processing. We divide parallel computers into three architectural configurations:  Pipeline computers  Array processors  multiprocessors 3.2.1 Pipeline Computers The process of executing an instruction in a digital computer involves 4 major steps  Instruction fetch 15  Instruction decoding  Operand fetch  Execution In a pipelined computer successive instructions are executed in an overlapped fashion. In a non pipelined computer these four steps must be completed before the next instructions can be issued.  Instruction fetch : Instruction is fetched from the main memory  Instruction decoding: Identifying the operation to be performed.  Operand Fetch: If any operands is needed is fetched.  Execution : Execution of the Arithmetic and logical operation An instruction cycle consists of multiple pipeline cycles. The flow of data (input operands, intermediate results and output results) from stage to stage is triggered by a common clock of the pipeline. The operations of all stages are triggered by a common clock of the pipeline. For non pipelined computer, it takes four pipeline cycles to complete one instruction. Once a pipe line is filled up, an output result is produced from the pipeline on each cycle. The th instruction cycle has been effectively reduced to 1/4 of the original cycle time by such overlapped execution. Processor S S S S S 0 1 2 3 4 Figure 3.1 A pipelined Processor Figure 3.2 Space Diagram for a Pipelined Processor 3.2.2 Array Processors An array processor is a synchronous parallel computer with multiple arithmetic logic units called processing elements (PE) that can operate in parallel in lock step fashion. 16 By replication one can achieve spatial parallelism. The PEs are synchronized to perform the same function at the same time. Scalar and control type of instructions are directly executed in the control unit (CU). Each PE consists of an ALU registers and a local memory. The PEs are interconnected by a data- routing network. Vector instructions are broadcasted to the PEs for distributed execution over different component operands fetched directly from local memories. Array processors designed with associative memories are called as associative processors. Figure 3.3 Functional structure of a modern pipeline computer with scalar and vector capabilities 3.2.3 Multiprocessor Systems A basic multiprocessor contains two or more processors of comparable capabilities. All processors share access to common sets of memory modules, I/O channels and peripheral devices. The entire system must be controlled by a single integrated operating system providing interactions between processors and their programs at various levels. Multiprocessor hardware system organization is determined by the interconnection structure to be used between the memories and processors. Three different interconnection are  Time shared Common bus  Cross Bar switch network  Multiport memories 3.3 Let us Sum Up A pipeline computer performs overlapped computations to exploit temporal parallelism. An array processor uses multiple synchronized arithmetic and logic units to achieve spatial parallelism. A multiprocessor system achieves asynchronous parallelism through a set of interactive processors with shared resources. 17 3.4 Lesson-end Activities 1.Discuss how instructions are executed in a pipelined processor. 2.What are the 2 methods in which array processors can be implemented? Discuss. 3.5 Points for Discussions The fundamental difference between an array processor and a multiprocessor system is that the processing elements in an array processor operate synchronously but processors in a multiprocessor systems may not operate synchronously. 3.6 References From Net : Tarek A. El-Ghazawi, Dept. of Electrical and Computer Engineering, The George Washington University 18 Lesson 4 : Architectural Classification Schemes Contents: 4.0 Aims and Objectives 4.1 Introduction 4.2 Architectural Classification Schemes 4.2.1 Flynn’s Classification 4.2.1.1 SISD 4.2.1.2 SIMD 4.2.1.3 MISD 4.2.1.4 MIMD 4.2.2 Feng’s Classification 4.2.3 Handler’s Classification 4.3 Let us Sum Up 4.4 Lesson-end Activities 4.5 Points for discussions 4.6 References 4 Aims and Objectives The main objective is to learn various architectural classification schemes, Flynn’s classification, Feng’s classification, and Handler’s Classification. 4.1 Introduction The Flynn’s classification scheme is based on the multiplicity of instruction streams and data streams in a computer system. Feng’s scheme is based on serial versus parallel processing. Handler’s classification is determined by the degree of parallelism and pipelining in various subsystem levels. 4.2 Architectural Classification Schemes 4.2.1 Flynn’s Classification The most popular taxonomy of computer architecture was defined by Flynn in 1966. Flynn's classification scheme is based on the notion of a stream of information. Two types of information flow into a processor: instructions and data. The instruction stream is defined as the sequence of instructions performed by the processing unit. The data stream is defined as the data traffic exchanged between the memory and the processing unit. According to Flynn's classification, either of the instruction or data streams can be single or multiple. Computer architecture can be classified into the following four distinct categories:  single-instruction single-data streams (SISD);  single-instruction multiple-data streams (SIMD);  multiple-instruction single-data streams (MISD); and 19  multiple-instruction multiple-data streams (MIMD). Conventional single-processor von Neumann computers are classified as SISD systems. Parallel computers are either SIMD or MIMD. When there is only one control unit and all processors execute the same instruction in a synchronized fashion, the parallel machine is classified as SIMD. In a MIMD machine, each processor has its own control unit and can execute different instructions on different data. In the MISD category, the same stream of data flows through a linear array of processors executing different instruction streams. In practice, there is no viable MISD machine; however, some authors have considered pipelined machines (and perhaps systolic-array computers) as examples for MISD. An extension of Flynn's taxonomy was introduced by D. J. Kuck in 1978. In his classification, Kuck extended the instruction stream further to single (scalar and array) and multiple (scalar and array) streams. The data stream in Kuck's classification is called the execution stream and is also extended to include single (scalar and array) and multiple (scalar and array) streams. The combination of these streams results in a total of 16 categories of architectures. 4.2.1.1 SISD Architecture  A serial (non-parallel) computer  Single instruction: only one instruction stream is being acted on by the CPU during any one clock cycle  Single data: only one data stream is being used as input during any one clock cycle  Deterministic execution  This is the oldest and until recently, the most prevalent form of computer  Examples: most PCs, single CPU workstations and mainframes Figure 4.1 SISD COMPUTER 20 4.2.1.2 SIMD Architecture  A type of parallel computer  Single instruction: All processing units execute the same instruction at any given clock cycle  Multiple data: Each processing unit can operate on a different data element  This type of machine typically has an instruction dispatcher, a very high-bandwidth internal network, and a very large array of very small-capacity instruction units.  Best suited for specialized problems characterized by a high degree of regularity, such as image processing.  Synchronous (lockstep) and deterministic execution  Two varieties: Processor Arrays and Vector Pipelines  Examples: o Processor Arrays: Connection Machine CM-2, Maspar MP-1, MP-2 o Vector Pipelines: IBM 9000, Cray C90, Fujitsu VP, NEC SX-2, Hitachi S820 Figure 4.2 SIMD COMPUTER CU-control unit PU-processor unit MM-memory module SM-Shared memory IS-instruction stream DS-data stream 4.2.1.3 MISD Architecture

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.