Avtomatik parallellashtirish - Automatic parallelization

Avtomatik parallellashtirish, shuningdek avtomatik parallellashtirish, yoki avtoparallelizatsiya ketma-ket konvertatsiya qilishni anglatadi kod ichiga ko'p tishli va / yoki vektorlangan umumiy xotirada bir vaqtning o'zida bir nechta protsessorlardan foydalanish uchun kod ko'p protsessor (SMP ) mashina. [1] Ketma-ket dasturlarni to'liq avtomatik ravishda parallellashtirish qiyin, chunki bu murakkablikni talab qiladi dasturni tahlil qilish va eng yaxshi yondashuv kompilyatsiya vaqtida ma'lum bo'lmagan parametr qiymatlariga bog'liq bo'lishi mumkinligi sababli.[2]

Avtoparallelizatsiya eng ko'p e'tiborni qaratadigan dasturiy boshqaruv tuzilmalari ko'chadan, chunki, umuman olganda, ko'pchilik ijro vaqti Dasturning qandaydir ko'chadan ichida amalga oshiriladi.Ilmalarni parallellashtirishda ikkita asosiy yondashuv mavjud: quvurli ko'p qirrali va tsikli ko'p yo'nalishli.[3] Masalan, har bir takrorlashda yuzta amalni bajaradigan va mingta takrorlanish uchun ishlaydigan tsiklni ko'rib chiqing. Buni 100 ta ustundan 1000 ta qatorga, jami 100000 ta operatsiyadan iborat panjara deb hisoblash mumkin. Ko'p tsiklli tsikl har bir qatorni har xil ipga belgilaydi. Pipelined multi-threading har bir ustunni har xil ipga tayinlaydi.

Avtomatik parallellashtirish texnikasi

Ajratish

Bu barcha statik va tashqi foydalanishlarni aniqlash uchun brauzer kirish manba fayllarini o'qiydigan birinchi bosqichdir. Fayldagi har bir satr ajratish uchun oldindan belgilangan naqshlar bo'yicha tekshiriladi nishonlar. Ushbu nishonlar keyinchalik thegrammar dvigatelida ishlatiladigan faylda saqlanadi. Grammatika mexanizmi koddagi o'zgaruvchilar, tsikllar, boshqaruv sozlamalari, funktsiyalar va boshqalarni aniqlash uchun oldindan belgilangan qoidalarga mos keladigan nishonlarning namunalarini tekshiradi.

Tahlil qiling

The analizator bir vaqtning o'zida bajarilishi mumkin bo'lgan kod bo'limlarini aniqlash uchun ishlatiladi. Analizator brauzer-tahlilchi tomonidan taqdim etilgan statik ma'lumotlardan foydalanadi. Analizator dastlab barcha mustaqil funktsiyalarni topadi va ularni individual vazifalar sifatida belgilaydi. Keyin analizator qaysi vazifalarning bog'liqliklarini topadi.

Jadval

The rejalashtiruvchi barcha vazifalar va ularning bajarilishi va boshlanish vaqtlari bo'yicha bir-biriga bog'liqligini sanab chiqadi. Rejalashtiruvchi foydalaniladigan protsessorlar soni yoki dastur uchun bajarilishning umumiy vaqti bo'yicha eng maqbul jadvalni ishlab chiqaradi.

Kod ishlab chiqarish

The rejalashtiruvchi barcha vazifalar ro'yxatini va ular bajaradigan yadrolarning tafsilotlarini, ular bajaradigan vaqt bilan birga ishlab chiqaradi. Kod ishlab chiqaruvchisi kodga rejalashtiruvchi tomonidan bajarilishi paytida o'qiladigan maxsus tuzilmalarni kiritadi. Theseconstructs rejalashtiruvchiga ma'lum bir vazifani qaysi boshlanishini boshlash va tugash vaqtlari bilan birga bajarishini buyuradi.

Ko'p tsikli tsiklik

Parallellashtiruvchi davriy kompilyator davriy ravishda harakat qiladi pastadirni ajratish shuning uchun har biri takrorlash alohida-alohida bajarilishi mumkin protsessor bir vaqtning o'zida.

Kompilyatorni parallellashtirish tahlili

The kompilyator quyidagilarni aniqlash uchun odatda haqiqiy parallellashdan oldin ikkita tahlil o'tkazadi:

  • Loopni parallel qilish xavfsizmi? Bu savolga javob berish aniq bo'lishi kerak qaramlik tahlili va taxalluslarni tahlil qilish
  • Parallel qilish maqsadga muvofiqmi? Ushbu javob dasturning ish hajmini va parallel tizimning imkoniyatlarini ishonchli baholashni (modellashtirish) talab qiladi.

Tuzuvchining birinchi uzatmasi a bajaradi ma'lumotlarga bog'liqlikni tahlil qilish tsiklning har bir iteratsiyasi boshqalardan mustaqil ravishda bajarilishi mumkinligini aniqlash uchun tsiklning. Ma'lumotlarga bog'liqlik bilan ba'zan muomala qilish mumkin, ammo bu qo'shimcha xarajatlarni keltirib chiqarishi mumkin xabar o'tmoqda, sinxronizatsiya umumiy xotira, yoki protsessor bilan aloqa qilishning boshqa usuli.

Ikkinchi o'tish parallelizatsiyadan so'ng kodning nazariy bajarilish vaqtini kodning ketma-ket bajarilish vaqti bilan taqqoslash orqali parallellashtirish harakatlarini oqlashga harakat qiladi. Biroz qarama-qarshi bo'lib, kod har doim ham parallel bajarilishdan foyda ko'rmaydi. Bir nechta protsessorlardan foydalanish bilan bog'liq bo'lishi mumkin bo'lgan qo'shimcha xarajatlar paralellangan kodning potentsial tezlashishiga ta'sir qilishi mumkin.

Misol

Agar barcha takrorlashlar, har qanday chaqiruvda bir vaqtning o'zida bajarilishi mumkin bo'lsa, loop DOALL deb nomlanadi. Fortran quyidagi kod DOALL bo'lib, kompilyator tomonidan avtomatik parallellashtirilishi mumkin, chunki har bir iteratsiya boshqalardan mustaqil va massivning yakuniy natijasi z boshqa takrorlashlarning bajarilish tartibidan qat'iy nazar to'g'ri bo'ladi.

   qil men = 1, n     z(men) = x(men) + y(men)   enddo

Juda ko'p .. lar bor yoqimli ravishda parallel masalan, bunday DOALL ko'chadan muammolari. Masalan, qachon ko'rsatish izlangan film, filmning har bir kadri mustaqil ravishda namoyish etilishi mumkin va bitta kadrning har bir pikseli mustaqil ravishda namoyish etilishi mumkin.

Boshqa tomondan, quyidagi kodni avtomatik ravishda parallel qilib bo'lmaydi, chunki qiymati z (i) oldingi iteratsiya natijasiga bog'liq, z (i - 1).

   qil men = 2, n     z(men) = z(men - 1)*2   enddo

Bu kodni parallel qilish mumkin emas degani emas. Darhaqiqat, bu tengdir

   qil men = 2, n     z(men) = z(1)*2**(men - 1)   enddo

Biroq, hozirgi parallel ravishda tuzuvchi kompilyatorlar odatda bu parallelliklarni avtomatik ravishda chiqarishga qodir emaslar va bu kod birinchi navbatda parallellashtirishdan foyda keltiradimi degan savol tug'iladi.

Quvurli ko'p tarmoqli

Asosiy maqola: dasturiy quvurlarni uzatish

Quvurli ko'p tarmoqli parallellashtiruvchi kompilyator tsikl ichidagi operatsiyalar ketma-ketligini bir qator kod bloklariga ajratishga harakat qiladi, chunki har bir kod bloki alohida bajarilishi mumkin. protsessorlar bir vaqtning o'zida.

Bunday nisbatan mustaqil kod bloklariga, xususan foydalanadigan tizimlarga ega bo'lgan juda yoqimli parallel muammolar ko'p quvurlar va filtrlar.Masalan, jonli efirda televizion televizor ishlab chiqarishda quyidagi vazifalar soniyada bir necha marta bajarilishi kerak:

  1. Tasvir sensori ichidagi pikselli ma'lumotlarning bir qismini o'qing,
  2. Xom ma'lumotlarga MPEG kompensatsiyasi berilsinmi,
  3. Entropiya harakat vektorlarini va boshqa ma'lumotlarni siqadi,
  4. Siqilgan ma'lumotlarni paketlarga ajratish,
  5. Tegishli xatolarni tuzatishni qo'shing va ma'lumotlar paketlarini aylantirish uchun FFT qiling COFDM signallari va
  6. Televizor antennasidan COFDM signallarini yuboring.

Quvurli ko'p tarmoqli parallellashtiruvchi kompilyator ushbu 6 operatsiyaning har birini boshqacha protsessorga tayinlashi mumkin, ehtimol sistolik qator, bitta protsessorning chiqishini keyingi protsessorga yo'naltirish uchun tegishli kodni kiritish.

So'nggi tadqiqotlar GPU quvvatidan foydalanishga qaratilgan[4] va ko'p yadroli tizimlar[5] bunday mustaqil kod bloklarini (yoki oddiygina ko'chadan takrorlashni) ish vaqtida hisoblash. Kiritilgan xotira (to'g'ridan-to'g'ri yoki bilvosita), tsiklning turli xil takrorlanishi uchun oddiygina belgilanishi mumkin va bog'liqlikni aniqlash uchun taqqoslanishi mumkin. Ushbu ma'lumotdan foydalanib, takrorlashlar bir xil darajaga tegishli takrorlashlar bir-biridan mustaqil bo'lishi va parallel ravishda bajarilishi mumkin bo'lgan darajalarga guruhlangan.

Qiyinchiliklar

Quyidagi sabablarga ko'ra kompilyatorlar yoki asboblar tomonidan avtomatik ravishda parallellashtirish juda qiyin:[6]

  • qaramlikni tahlil qilish bilvosita adreslash, ko'rsatgichlar, rekursiya yoki bilvosita funktsiya chaqiruvlaridan foydalanadigan kod uchun qiyin, chunki kompilyatsiya vaqtida bunday bog'liqliklarni aniqlash qiyin;
  • tsikllarda noma'lum sonli takrorlanishlar mavjud;
  • global resurslarga kirishni xotirani ajratish, kiritish-chiqarish va umumiy o'zgaruvchilar nuqtai nazaridan muvofiqlashtirish qiyin;
  • tartibsiz algoritmlar kirishga bog'liq bo'lgan bilvosita kompilyatsiya vaqtini tahlil qilish va optimallashtirishga xalaqit beradi.[7]

Vaqtinchalik echim

To'liq avtomatik parallellashtirishning o'ziga xos qiyinchiliklari tufayli yuqori sifatli parallel dastur olish uchun bir nechta oson yondashuvlar mavjud. Ular:

  • Kabi dasturchilarga kompilyatorni parallellashtirishni boshqarish uchun dasturlariga "ko'rsatmalar" qo'shishiga ruxsat bering HPF uchun tarqatilgan xotira tizimlar va OpenMP yoki OpenHMPP uchun umumiy xotira tizimlar.
  • Dasturchilar va parallellashtiruvchi vositalar / kompilyatorlar o'rtasida interaktiv tizim yarating. Taniqli misollar Vektorli matolar Pareon, SUIF Explorer (Stenford universiteti oraliq formati kompilyatori), Polaris kompilyatori va ParaWise (rasmiy ravishda CAPTools).
  • Uskuna qo'llab-quvvatlanadi spekulyativ multithreading.

Kompilyatorlar va asboblarni parallellashtirish

Shuningdek qarang: Avtomatik parallellashtirish vositasi

Ko'pgina tadqiqotlar kompilyatorlar avtomatik parallellashtirish uchun o'ylab ko'ring Fortran dasturlar,[iqtibos kerak ] chunki Fortran kuchli kafolatlar beradi taxallus kabi tillarga qaraganda C. Odatiy misollar:

  • Paradigma kompilyatori
  • Polaris kompilyatori
  • Rays Fortran D kompilyatori
  • SUIF kompilyator
  • Vena Fortran kompilyatori

Adabiyotlar

  1. ^ "Yehezkael, Rafael (2000). "Hisoblash algoritmini dasturni tarqatish va aloqadan ajratish bo'yicha tajribalar". Springer Verlag kompyuter fanidan ma'ruza matnlari. Kompyuter fanidan ma'ruza matnlari. 1947: 268–278. doi: [// doi.org/10.1007%2F3-540-70734-4_32 10.1007 / 3-540-70734-4_32. ISBN  978-3-540-41729-3."]
  2. ^ Tulki, Jefri; Roy Uilyams; Pol Messina (1994). Parallel hisoblash ishlari!. Morgan Kaufmann. 575, 593 betlar. ISBN  978-1-55860-253-3.
  3. ^ Simone Kempanoni, Timoti Jons, Glenn Xollouey, Gu-Yon Vey, Devid Bruks."HELIX loyihasi: umumiy nuqtai va ko'rsatmalar".2012.
  4. ^ J Anantpur, R Govindarajan, ish vaqtiga bog'liqlikni hisoblash va heterojen tizimlarda tsikllarni bajarish "Arxivlangan nusxa" (PDF). Arxivlandi asl nusxasi (PDF) 2015-10-06 kunlari. Olingan 2015-10-05.CS1 maint: nom sifatida arxivlangan nusxa (havola)
  5. ^ X. Zhuang, A. E. Eyxenberger, Y. Luo, Kevin O'Brayen, Ketrin, Parallellikdan qaramlikdan xabardor rejalashtirish bilan foydalanish
  6. ^ "Avtomatik parallellik va ma'lumotlarga bog'liqlik". Arxivlandi asl nusxasi 2014-07-14.
  7. ^ Rünger, Gudula (2006). "Noto'g'ri algoritmlarni dasturlashning parallel modellari". Parallel algoritmlar va klasterlarni hisoblash. Hisoblash fanlari va muhandislik fanidan ma'ruza matnlari. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN  978-3-540-33539-9.

Shuningdek qarang