Tugas Pengantar Komputasi Modern

 Tugas Penulisan Artikel Pada Blog

1.1 Apa itu Komputasi Pararel ?
Dalam arti yang paling sederhana, komputasi paralel adalah penggunaan simultan dari beberapa sumber komputasi sederhana yang digunakan untuk memecahkan suatu masalah komputasi dengan:

• Masalah dipecah menjadi bagian-bagian terpisah yang dapat dipecahkan secara bersamaan
• Setiap bagian selanjutnya dipecah menjadi serangkaian instruksi
• Instruksi dari setiap bagian dijalankan secara bersamaan pada prosesor yang berbeda
• Keseluruhan mekanisme kontrol / koordinasi digunakan

1.2 Mengapa Menggunakan Komputasi Paralel?
Dikehidupan nyata, massively parallel banyak ditemui pada :

1. Di alam, banyak hal kompleks yang merupakan sebuah peristiwa terkait  dan  terjadi pada saat yang sama, namun terurut secara temporal.
2. Dibandingkan dengan komputasi serial, komputasi parallel jauh lebih cocok  dengan permodelan, simulasi dan memahami fenomena yang kompleks di dunia nyata.

Berikut alasan utama menggunakan komputer pararel :

1. Hemat waktu dan/ atau uang
2. Memecahkan masalah yang lebih besar / lebih kompleks
3. Memberikan concurrency
4. Ambil keunggulan sumber daya non local
5. Membuat hardware pararel yang lebih baik

1.3 Siapa yang menggunakan Komputer pararel ?

• Sains dan Teknik
• Industri dan komersial
• Aplikasi Global

2. Konsep dan Terminologi

2.1 Arsitektur Covon Neumann

Dinamai setelah ahli matematika / genius Hungaria John von Neumann yang pertama kali menulis persyaratan umum untuk komputer elektronik dalam makalahnya tahun 1945. Juga dikenal sebagai "komputer program tersimpan" - instruksi dan data program disimpan dalam memori elektronik. Berbeda dari komputer sebelumnya yang diprogram melalui "kabel keras". Sejak itu, hampir semua komputer telah mengikuti desain dasar ini:

2.2 Taksonomi Klasik Flynn

Ada berbagai cara untuk mengklasifikasikan komputer paralel. Salah satu klasifikasi yang lebih banyak digunakan, digunakan sejak 1966, disebut Flynn's Taxonomy. 

• Taksonomi Flynn membedakan arsitektur komputer multi-prosesor sesuai dengan bagaimana mereka dapat diklasifikasikan di sepanjang dua dimensi independen dari Instruction Stream dan Data Stream. Masing-masing dimensi ini hanya dapat memiliki satu dari dua status yang mungkin: Tunggal atau Banyak.
• Matriks di bawah mendefinisikan 4 mungkin klasifikasi menurut Flynn, 
• 

2.3 Beberapa Terminologi Paralel Umum

Seperti yang lainnya, komputasi paralel memiliki "jargon" sendiri. Beberapa istilah yang lebih umum digunakan terkait dengan komputasi paralel tercantum di bawah ini.

• CPU / Soket / Prosesor / Inti
• Pipelining
• Shared Memory
• Symmetric Multi-Processor (SMP)
• Distributed Memory
• Communications
• Synchronization
• Granularity
• Observed Speedup
• Parallel Overhead
• Massively Parallel
• Embarrassingly Parallel
• Scalability

2.4 Batas dan Biaya Pemrograman Paralel

Amdahl's Law:
Hukum Amdahl menyatakan bahwa potensi program speedup ditentukan oleh fraksi kode (P) yang dapat diparalelkan

Kompleksitas:
Secara umum, aplikasi paralel jauh lebih kompleks daripada aplikasi serial yang sesuai, mungkin urutan besarnya. Anda tidak hanya memiliki beberapa aliran instruksi yang dieksekusi pada saat yang sama, tetapi Anda juga memiliki data yang mengalir di antaranya.

Portability:
Berkat standardisasi di beberapa API, seperti MPI, thread POSIX, dan OpenMP, masalah portabilitas dengan program paralel tidak seserius tahun-tahun sebelumnya. Namun..

Resource Requirements:
Tujuan utama pemrograman paralel adalah untuk mengurangi waktu eksekusi jam dinding, namun untuk mencapai ini, lebih banyak waktu CPU diperlukan. Sebagai contoh, kode paralel yang berjalan dalam 1 jam pada 8 prosesor sebenarnya menggunakan 8 jam waktu CPU.

Scalability:
Pustaka dukungan paralel dan perangkat lunak subsistem dapat membatasi skalabilitas terlepas dari aplikasi Anda.

3. Arsitektur Memori Komputer Paralel

3.1 Shared Memory

Karektiristik umum:

• Memori paralel komputer bersama sangat bervariasi, tetapi umumnya memiliki kemampuan yang sama untuk semua prosesor untuk mengakses semua memori sebagai ruang alamat global Beberapa prosesor dapat beroperasi secara independen tetapi berbagi sumber daya memori yang sama. 
• Perubahan lokasi memori yang dipengaruhi oleh satu prosesor dapat dilihat oleh semua prosesor lainnya.

Uniform Memory Access (UMA):

Paling umum diwakili hari ini oleh mesin Symmetric Multiprocessor (SMP) Prosesor identic Akses yang sama dan waktu akses ke memori Kadang-kadang disebut CC-UMA, Cache Coherent UMA. Cache coherent berarti jika satu prosesor memperbarui lokasi dalam memori bersama, semua prosesor lain tahu tentang pembaruan tersebut. Koherensi cache dicapai pada tingkat perangkat keras.

3.2 Distributed Memory

General Characteristics
Seperti sistem memori bersama, sistem memori terdistribusi sangat bervariasi tetapi berbagi karakteristik umum. Sistem memori terdistribusi memerlukan jaringan komunikasi untuk menghubungkan memori antar-prosesor

Advantages:
Memori dapat diskalakan dengan jumlah prosesor. Tambah jumlah prosesor dan ukuran memori bertambah secara proporsional.

Disadvantages:
Programmer bertanggung jawab atas banyak detail yang terkait dengan komunikasi data antar prosesor.

3.3 Hybrid Distributed-Shared Memory

Karakteristik umum:

Komputer terbesar dan tercepat di dunia saat ini menggunakan arsitektur memori bersama dan didistribusikan.

Keuntungan dan kerugian:

Apa pun yang umum untuk arsitektur memori bersama dan didistribusikan.

4. Model Pemrograman Paralel

4.1 Model Memori Bersama (tanpa utas)

• Dalam model pemrograman ini, proses / tugas berbagi ruang alamat bersama, yang mereka baca dan tulis secara asinkron.
• Berbagai mekanisme seperti kunci / semafor digunakan untuk mengontrol akses ke memori bersama, menyelesaikan perselisihan dan untuk mencegah kondisi balapan dan kebuntuan.

Implementasi :

Pada mesin memori bersama yang berdiri sendiri, sistem operasi asli, kompiler dan / atau perangkat keras menyediakan dukungan untuk pemrograman memori bersama. Sebagai contoh, standar POSIX menyediakan API untuk menggunakan memori bersama, dan UNIX menyediakan segmen memori bersama (shmget, shmat, shmctl, dll)

4.2 Threads Model

Model pemrograman ini adalah jenis pemrograman memori bersama.

Dalam model thread pemrograman paralel, proses "beban berat" tunggal dapat memiliki beberapa "bobot ringan", jalur eksekusi bersamaan.

Implementasi :

Dari perspektif pemrograman, implementasi utas biasanya terdiri dari:

Perpustakaan subrutin yang dipanggil dari dalam kode sumber paralel

Seperangkat arahan kompiler yang tertanam dalam kode sumber serial atau parallel.

4.3 Distributed Memory / Message Passing Model

Model ini menunjukkan karakteristik berikut:

Serangkaian tugas yang menggunakan memori lokal mereka sendiri selama perhitungan. Banyak tugas dapat berada di mesin fisik yang sama dan / atau di sejumlah mesin yang sewenang-wenang.

Implementasi :

• Dari perspektif pemrograman, implementasi message passing biasanya terdiri dari perpustakaan subrutin. Panggilan ke subrutin ini tertanam dalam kode sumber. Programmer bertanggung jawab untuk menentukan semua paralelisme.
• Secara historis, berbagai pustaka lewat pesan telah tersedia sejak 1980-an. Implementasi ini sangat berbeda satu sama lain sehingga menyulitkan programmer untuk mengembangkan aplikasi portabel.
• Pada tahun 1992, Forum MPI dibentuk dengan tujuan utama membangun antarmuka standar untuk implementasi message passing.

4.4 Data Parallel Model

• Pada arsitektur memori bersama, semua tugas mungkin memiliki akses ke struktur data melalui memori global.
• Pada arsitektur memori terdistribusi, struktur data global dapat dibagi secara logis dan / atau secara fisik di seluruh tugas.

Implementasi :

Saat ini, ada beberapa implementasi pemrograman paralel yang relatif populer, dan terkadang pengembangan, berdasarkan pada model Data Parallel / PGAS.

Coarray Fortran: satu set kecil ekstensi ke Fortran 95 untuk pemrograman paralel SPMD. Ketergantungan kompilator. Informasi lebih lanjut: https://en.wikipedia.org/wiki/Coarray_Fortran

Unified Parallel C (UPC): ekstensi ke bahasa pemrograman C untuk pemrograman paralel SPMD. Ketergantungan kompilator. Informasi lebih lanjut: http://upc.lbl.gov/

4.5 Hybrid Model

• Saat ini, ada beberapa implementasi pemrograman paralel yang relatif populer, dan terkadang pengembangan, berdasarkan pada model Data Parallel / PGAS.
• Coarray Fortran: satu set kecil ekstensi ke Fortran 95 untuk pemrograman paralel SPMD. Ketergantungan kompilator. Informasi lebih lanjut: https://en.wikipedia.org/wiki/Coarray_Fortran
• Unified Parallel C (UPC): ekstensi ke bahasa pemrograman C untuk pemrograman paralel SPMD. Ketergantungan kompilator. Informasi lebih lanjut: http://upc.lbl.gov/...

4.6 SPMD and MPMD

Single Program Multiple Data (SPMD):

SPMD sebenarnya adalah model pemrograman "tingkat tinggi" yang dapat dibangun berdasarkan kombinasi dari model pemrograman paralel yang disebutkan sebelumnya.

Multiple Program Multiple Data (MPMD):

• Seperti SPMD, MPMD sebenarnya adalah model pemrograman "tingkat tinggi" yang dapat dibangun di atas kombinasi model pemrograman paralel yang disebutkan sebelumnya.
• PROGRAM GANDA: Tugas dapat menjalankan program yang berbeda secara bersamaan. Program dapat berupa utas, pesan yang dikirimkan, paralel data atau hibrid

5. Designing Parallel Programs

Automatic vs. Manual Parallelization

Fully Automatic

Kompiler menganalisis kode sumber dan mengidentifikasi peluang untuk paralelisme.

Analisis ini termasuk mengidentifikasi inhibitor terhadap paralelisme dan mungkin pembobotan biaya pada apakah paralelisme benar-benar akan meningkatkan kinerja.

Loop adalah target yang paling sering untuk paralelisasi otomatis.

Programmer Directed

Menggunakan "compiler directives" atau flag compiler, programmer secara eksplisit memberi tahu kompiler bagaimana cara memparalelkan kode.

Mungkin dapat digunakan bersamaan dengan beberapa derajat paralelisasi otomatis juga.

Pahami Masalah dan Programnya

Tidak diragukan lagi, langkah pertama dalam mengembangkan perangkat lunak paralel adalah terlebih dahulu memahami masalah yang ingin Anda selesaikan secara paralel. Jika Anda memulai dengan program serial, ini perlu memahami kode yang ada juga.

menghambat inhibitor terhadap paralelisme. Satu kelas umum dari inhibitor adalah ketergantungan data, seperti yang ditunjukkan oleh urutan Fibonacci di atas.

Selidiki algoritma lain jika memungkinkan. Ini mungkin merupakan pertimbangan paling penting saat merancang aplikasi paralel.

Partitioning

Salah satu langkah pertama dalam merancang program paralel adalah memecah masalah menjadi "bongkahan" diskrit pekerjaan yang dapat didistribusikan ke berbagai tugas. Ini dikenal sebagai dekomposisi atau partisi.

Ada dua cara dasar untuk mempartisi kerja komputasi di antara tugas paralel: dekomposisi domain dan dekomposisi fungsional.

Communications

Siapa yang Membutuhkan Komunikasi?

Kebutuhan akan komunikasi antar tugas tergantung pada masalah Anda:

Synchronization

Mengelola urutan pekerjaan dan tugas yang dilakukan adalah pertimbangan desain kritis untuk sebagian besar program paralel.

Dapat menjadi faktor penting dalam kinerja program (atau kurang dari itu)

Seringkali membutuhkan "serialisasi" segmen program

Data Dependencies

Definisi:

Ketergantungan ada antara pernyataan program ketika urutan pelaksanaan pernyataan mempengaruhi hasil program.

Ketergantungan data dihasilkan dari beberapa penggunaan lokasi yang sama dalam penyimpanan oleh tugas yang berbeda.

Ketergantungan penting untuk pemrograman paralel karena mereka adalah salah satu penghambat utama paralelisme.

Load Balancing

Load balancing sesuai dengan jumlah keseluruhan pekerjaan yang sama di antara tugas-tugas sehingga semua tugas tetap sibuk sepanjang waktu. Ini dapat dianggap sebagai minimalisasi waktu tugas idle.

Load balancing penting untuk program paralel karena alasan kinerja. Sebagai contoh, jika semua tugas menyetujui pada titik penyelesaian penghalang, tugas paling lambat akan menentukan persetujuan keseluruhan.

Granularity

Rasio Komputasi / Komunikasi:

Dalam komputasi paralel, granularitas adalah ukuran kualitatif rasio komputasi terhadap komunikasi.

Periode perhitungan biasanya dipisahkan dari periode komunikasi dengan peristiwa sinkronisasi.

Paralelisme fine-grain:

Sejumlah kecil pekerjaan komputasi dilakukan antara acara komunikasi

Komputasi rendah untuk rasio komunikasi

Memfasilitasi penyeimbangan muatan

Menyiratkan overhead komunikasi yang tinggi dan lebih sedikit peluang untuk peningkatan kinerja

Jika granularity terlalu halus, ada kemungkinan overhead yang diperlukan untuk komunikasi dan sinkronisasi antara tugas lebih lama dari perhitungan.

Coarse-grain Parallelism:

Sejumlah besar pekerjaan komputasi dilakukan antara komunikasi / sinkronisasi peristiwa

Komputasi tinggi untuk rasio komunikasi

Mengimplikasikan lebih banyak peluang untuk peningkatan kinerja

Sulit untuk memuat keseimbangan secara efisien

 Mana yang Terbaik?

Granularity yang paling efisien tergantung pada algoritma dan lingkungan perangkat keras tempat ia beroperasi.

Dalam kebanyakan kasus, overhead yang terkait dengan komunikasi dan sinkronisasi relatif tinggi terhadap kecepatan eksekusi sehingga menguntungkan untuk memiliki granularity kasar.

Paralelisme butiran halus dapat membantu mengurangi overhead karena ketidakseimbangan beban.

I/O

Berita Buruk:

Operasi I / O umumnya dianggap sebagai penghambat paralelisme.

Operasi I / O membutuhkan pesanan lebih banyak waktu daripada operasi memori.

Sistem I / O paralel mungkin belum matang atau tidak tersedia untuk semua platform.

Dalam lingkungan di mana semua tugas melihat ruang file yang sama, operasi tulis dapat mengakibatkan penimpaan file.

Operasi baca dapat dipengaruhi oleh kemampuan server file untuk menangani beberapa permintaan baca sekaligus.

I / O yang harus dilakukan melalui jaringan (NFS, non-lokal) dapat menyebabkan kemacetan parah dan bahkan crash server file.

Berita bagus:

- Sistem file paralel tersedia. Sebagai contoh:

GPFS: Sistem File Paralel Umum (IBM). Sekarang disebut IBM Spectrum Scale.

Lustre: untuk cluster Linux (Intel)

HDFS: Sistem File Terdistribusi Hadoop (Apache)

PanFS: Panasas ActiveScale File System untuk cluster Linux (Panasas, Inc.)

Dan banyak lagi - lihat http://en.wikipedia.org/wiki/List_of_file_systems#Distributed_parallel_file_systems

-Spesifikasi antarmuka pemrograman I / O paralel untuk MPI telah tersedia sejak 1996 sebagai bagian dari MPI-2. Implementasi vendor dan "gratis" sekarang umumnya tersedia.

Debugging

Debugging kode paralel bisa sangat sulit, terutama karena kode meningkat ke atas.

Kabar baiknya adalah bahwa ada beberapa pengadu yang hebat yang tersedia untuk membantu:

Berulir - pthreads dan OpenMP

MPI

GPU / akselerator

Hibrida

Performance Analysis and Tuning

Seperti halnya debugging, menganalisis dan menyetel kinerja program paralel dapat jauh lebih menantang daripada untuk program serial.

Untungnya, ada sejumlah alat yang sangat baik untuk analisis dan penyetelan kinerja program paralel.

Pengguna Livermore Computing memiliki akses ke beberapa alat tersebut, yang sebagian besar tersedia di semua kluster produksi.

6. Parallel Examples

Array Processing

Contoh ini menunjukkan perhitungan pada elemen array 2 dimensi; suatu fungsi dievaluasi pada setiap elemen array.

Perhitungan pada setiap elemen array tidak tergantung dari elemen array lainnya.

Masalahnya adalah komputasi intensif.

Program serial menghitung satu elemen pada suatu waktu secara berurutan.

PI Calculation

Nilai PI dapat dihitung dengan berbagai cara. Pertimbangkan metode perkiraan Monte Carlo:

Tuliskan lingkaran dengan jari-jari r dalam kotak dengan panjang sisi 2r

Luas lingkaran adalah Πr2 dan luas persegi adalah 4r2

Rasio luas lingkaran dengan luas bujur sangkar adalah:

Πr2 / 4r2 = Π / 4

Jika Anda secara acak menghasilkan N poin di dalam kotak, kira-kira

N * Π / 4 titik tersebut (M) harus berada di dalam lingkaran.

Π kemudian diperkirakan sebagai:

N * Π / 4 = M

Π / 4 = M / N

Π = 4 * M / N

Perhatikan bahwa meningkatkan jumlah titik yang dihasilkan meningkatkan perkiraan.

Simple Heat Equation

Sebagian besar masalah dalam komputasi paralel memerlukan komunikasi di antara tugas-tugas tersebut. Sejumlah masalah umum memerlukan komunikasi dengan tugas "tetangga".

Persamaan panas 2-D menggambarkan perubahan suhu dari waktu ke waktu, mengingat distribusi suhu awal dan kondisi batas.

Perhitungan elemen tergantung pada nilai elemen tetangga:

1-D Wave Equation Parallel Solution

Ini adalah contoh lain dari masalah yang melibatkan ketergantungan data. Solusi paralel akan melibatkan komunikasi dan sinkronisasi.

Seluruh array amplitudo dipartisi dan didistribusikan sebagai subarrays ke semua tugas. Setiap tugas memiliki porsi yang sama dari total array.

Load balancing: semua titik membutuhkan kerja yang sama, sehingga poin harus dibagi secara merata

Dekomposisi blok akan membuat pekerjaan dipartisi ke dalam sejumlah tugas sebagai potongan, yang memungkinkan setiap tugas untuk memiliki sebagian besar titik data yang berdekatan.

Kebutuhan komunikasi hanya terjadi pada batas data. Semakin besar ukuran blok semakin sedikit komunikasi.

·