Transcript Slide 1
Pendahuluan Algoritma Pengolahan Paralel S1-TI Prepared by: MT Wilson Komputasi Paralel • Google runs on a distributed network of thousands of low-cost computers and can therefore carry out fast parallel processing • Parallel processing is a method of computation in which many calculations can be performed simultaneously, significantly speeding up data processing. Parallel Processing vs Multitasking • Parallel processing = menjalankan satu program lebih dari satu CPU • Multitasking = CPU seakan-akan menjalankan instruksi-instruksi dari program-program yang berbeda dengan berpindah-pindah dari satu program ke program lain dengan cepat Synchronous v Asynchronous • Synchronous memungkinkan paralelisme hanya sebagai satu “langkah”. Sebuah program memecah “langkah” tersebut menjadi sebuah rangkaian langkah-langkah. Paralelisme difasilitasi dengan pengerjaan masing-masing langkah pada banyak prosesor. Pendekatan ini diasosiasikan dengan model SIMD (Single Instruction, Multiple Data) Synchronous v Asynchronous (2) • The SIMD Model (Single Instruction, Multiple Data) lends itself well to the automobile assembly line analogy. In this scenario, one worker executes the same task (single instruction) on multiple cars (multiple data) as they come down the assembly line. This worker does not have a choice of tasks and is dependent on the arrival of data (automobile) to perform the task. Synchronous v Asynchronous (3) • Asynchronous program dianggap sebagai rangkaian proses yang berurutan yang saling berinteraksi, tapi diproses secara terpisah. Sebuah proses program dianggap diproses secara asinkronos. Jika sebuah proses membutuhkan informasi dari proses lain, proses ini mungkin harus menunggu informasi itu sampai tersedia, tapi proses lain tidak terpengaruh dengan interaksi ini. Model ini diasosiasikan dengan model MIMD (Multiple Instruction Multiple Data stream) Synchronous v Asynchronous (3) • MIMD model is equivalent to a modern day assembly plant and is the fastest and most efficient model. In this example, our plant is required to build 100 cars. Here, multiple assembly lines are given instructions (multiple instructions) to build automobiles all contributing to the goal of building 100 cars. Each assembly line is assigned a number of cars to assemble (multiple data) and works independently of every other line. The speed with which one line is able to complete a car does not affect the speed of the other lines. Instructions for what each line will do comes from management who oversees and coordinates the work. Control v Data Paralellism • Two distinct types of parallelism can be found in today's parallel computers - Control parallel and Data parallel. • Control parallel computers achieve increased performance by taking advantage of parallelism found in the control structure of the program. In these machines each processor executes a portion of the program. • Data parallel computers achieve increased performance by taking advantage of the parallelism found in the data of a problem. The machines consist of a single instruction engine and thousands of data processors each having local memory, connected to a communications network over which they may exchange information with other processors.