Algoritma Paralel dan Kinerja

Desain algoritma paralel mencari komputasi yang menunjukkan paralelisme melimpah dengan komunikasi rendah, dan analisis kinerja mengukur seberapa baik algoritma tersebut memanfaatkan prosesor tambahan.

Definition

Algoritma paralel menentukan bagaimana suatu masalah diselesaikan oleh beberapa prosesor yang bekerja sama; kualitasnya dinilai berdasarkan kerja (total operasi) dan kedalaman (rantai ketergantungan terpanjang), serta metrik kinerja seperti speedup dan efisiensi yang mengukur manfaat penggunaan p prosesor.

Scope

Topik ini mencakup model untuk merancang dan menganalisis algoritma paralel—terutama PRAM dan analisis kerja-kedalamannya—desain primitif paralel seperti penjumlahan prefiks (scan), reduksi, dan pengurutan, serta kerangka kerja kinerja dari speedup, efisiensi, optimalitas biaya, isoefisiensi, dan hukum skala Amdahl dan Gustafson. Ini menyediakan dasar analitis untuk penalaran tentang program paralel di semua model pemrograman.

Core questions

• Bagaimana paralelisme inheren suatu masalah dicirikan oleh kerja dan kedalamannya?
• Bagaimana speedup, efisiensi, dan skalabilitas didefinisikan dan diukur?
• Bagaimana fraksi serial atau pertumbuhan suatu masalah menentukan skalabilitas paralelnya?

Key theories

PRAM dan analisis kerja-kedalaman

Model PRAM mengidealkan mesin paralel dengan memori bersama dan langkah-langkah sinkron, mendukung analisis kerja algoritma (total operasi) dan kedalaman (panjang jalur kritis), yang bersama-sama membatasi waktu paralel yang dapat dicapai.

Speedup, efisiensi, dan isoefisiensi

Speedup mengukur seberapa cepat p prosesor menyelesaikan suatu masalah, efisiensi menormalkannya per prosesor, dan isoefisiensi menyatakan bagaimana ukuran masalah harus tumbuh dengan jumlah prosesor untuk menjaga efisiensi konstan, menangkap skalabilitas.

Hukum Amdahl dan Gustafson

Hukum Amdahl membatasi speedup ukuran tetap oleh fraksi serial, sementara hukum Gustafson mengamati bahwa penskalaan masalah dengan mesin memungkinkan speedup yang mendekati linier, secara bersama-sama membingkai penskalaan kuat versus penskalaan lemah.

Clinical relevance

Analisis kerja-kedalaman dan hukum skala memandu apakah dan bagaimana suatu komputasi harus diparalelkan dan memprediksi perilakunya pada skala, menginformasikan desain segala sesuatu mulai dari pengurutan dan kernel graf hingga simulasi besar dan pelatihan pembelajaran mesin.

History

Argumen Amdahl tahun 1967 dan sanggahan Gustafson tahun 1988 membingkai perdebatan speedup; model PRAM dan kerangka kerja kerja-kedalaman berkembang sepanjang tahun 1980-an dan dikodifikasi dalam teks JaJa tahun 1992 serta analisis skalabilitas oleh Grama dan rekan-rekannya, memberikan komputasi paralel inti teoretisnya.

Debates

Penskalaan kuat versus penskalaan lemah

Pandangan penskalaan kuat Amdahl (masalah tetap, lebih banyak prosesor) memprediksi hasil yang semakin berkurang, sementara pandangan penskalaan lemah Gustafson (perbesar masalah dengan prosesor) memprediksi speedup yang berkelanjutan; ukuran yang tepat tergantung pada apakah ukuran masalah atau waktu-ke-solusi yang ditetapkan.

Key figures

• Joseph JaJa
• Gene Amdahl
• John Gustafson
• Vipin Kumar

Seminal works

• jaja1992
• amdahl1967
• gustafson1988

Frequently asked questions

Apa perbedaan antara kerja dan kedalaman algoritma paralel?

Kerja adalah jumlah total operasi yang dilakukan di semua prosesor, sedangkan kedalaman (atau rentang) adalah panjang rantai operasi yang saling bergantung terpanjang. Kedalaman membatasi waktu eksekusi paralel terbaik yang mungkin, dan rasio kerja-terhadap-kedalaman menunjukkan seberapa banyak paralelisme yang tersedia.