Karp-Flatt metrikasi - Karp–Flatt metric

Ushbu maqolada a foydalanilgan adabiyotlar ro'yxati, tegishli o'qish yoki tashqi havolalar, ammo uning manbalari noma'lum bo'lib qolmoqda, chunki u etishmayapti satrda keltirilgan. Iltimos yordam bering yaxshilash tomonidan ushbu maqola tanishtirish aniqroq iqtiboslar. (2020 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

The Karp-Flatt metrikasi ning o'lchovidir parallellashtirish kodi parallel protsessor tizimlar. Ushbu ko'rsatkich qo'shimcha ravishda mavjud Amdahl qonuni va Gustafson qonuni ma'lum bir kompyuter kodining parallelligi darajasining ko'rsatkichi sifatida. 1990 yilda Alan H. Karp va Horace P. Flatt tomonidan taklif qilingan.

Tavsif

Ko'rgazmali parallel hisoblash berilgan tezlikni oshirmoq ${displaystyle psi}$ kuni ${displaystyle p}$ protsessorlar, qaerda ${displaystyle p}$ > 1, eksperimental ravishda aniqlangan ketma-ket kasr ${displaystyle e}$ Karp-Flatt Metric vizasi sifatida aniqlanadi:

${displaystyle e = {frac {{frac {1} {psi}} - {frac {1} {p}}} {1- {frac {1} {p}}}}}$

Ning qiymati qancha past bo'lsa ${displaystyle e}$, parallellashtirish qanchalik yaxshi bo'lsa.

Asoslash

A ning ishlash ko'rsatkichlarini o'lchashning ko'plab usullari mavjud parallel algoritm parallel protsessorda ishlash. Karp-Flatt metrikasi metrikani aniqlaydi, bu ko'rsatkichning boshqa ko'rsatkichlardan oson farq qilmaydigan tomonlarini ochib beradi. Turlarning psevdo- "hosilasi" quyidagidan kelib chiqadi Amdahl qonuni quyidagicha yozilishi mumkin:

${displaystyle T (p) = T_ {s} + {frac {T_ {p}} {p}}}$

Qaerda:

• ${displaystyle T (p)}$ bu kodni bajarish uchun sarflangan umumiy vaqt ${displaystyle p}$- protsessor tizimi
• ${displaystyle T_ {s}}$ kodning ketma-ket qismi ishlashga ketadigan vaqt
• ${displaystyle T_ {p}}$ kodning parallel qismi bitta protsessorda ishlashiga sarf qilingan vaqt
• ${displaystyle p}$ bu protsessorlarning soni

almashtirish bilan olingan natija bilan ${displaystyle p}$ = 1 ta. ${displaystyle T (1) = T_ {s} + T_ {p}}$, agar biz seriyali kasrni aniqlasak ${displaystyle e}$ = ${displaystyle {frac {T_ {s}} {T (1)}}}$ keyin tenglamani quyidagicha yozish mumkin

${displaystyle T (p) = T (1) e + {frac {T (1) (1-e)} {p}}}$

Jihatidan tezlikni oshirmoq ${displaystyle psi}$ = ${displaystyle {frac {T (1)} {T (p)}}}$ :

${displaystyle {frac {1} {psi}} = e + {frac {1-e} {p}}}$

Ketma-ket fraktsiyani echib, biz yuqoridagi kabi Karp-Flatt metrikasini olamiz. E'tibor bering, bu Amdahl qonunidan "kelib chiqish" emas, chunki chap tomon a ni ifodalaydi metrik matematik jihatdan olingan miqdor emas. Yuqoridagi muolaja shunchaki Karp-Flatt metrikasining Amdahl qonuniga mos kelishini ko'rsatadi.

Foydalanish

E seriyali fraktsiyasi ko'pincha esga olinadi Kompyuter fanlari adabiyot, u kamdan-kam hollarda diagnostika vositasi sifatida ishlatilgan tezlikni oshirmoq va samaradorlik bor. Karp va Flatt ushbu ko'rsatkichni taklif qilish orqali buni tuzatishga umid qilishdi. Ushbu ko'rsatkich kompyuter kodining parallelligini o'lchash uchun ishlatiladigan boshqa qonunlar va miqdorlarning etishmovchiligini ko'rib chiqadi. Xususan, Amdahl qonuni hisobga olinmaydi yuklarni muvozanatlash masalalar, va buni qabul qilmaydi tepada hisobga olish. Ketma-ket fraktsiyani metrik sifatida ishlatish boshqalarga nisbatan aniq afzalliklarga ega, ayniqsa protsessorlar soni ko'payib boradi.

Ruxsat etilgan o'lchamdagi muammo uchun, parallel hisoblash samaradorligi odatda protsessorlar sonining ko'payishi bilan kamayadi. Karp-Flatt metrikasi yordamida eksperimental ravishda olingan ketma-ket fraksiyondan foydalanib, samaradorlikning pasayishi parallellik imkoniyatlarining cheklanganligi yoki algoritmik yoki me'moriy xarajatlarning ko'payishi bilan bog'liqligini aniqlashimiz mumkin.

Adabiyotlar

• Karp, Alan H. va Flatt, Horace P. (1990). "Parallel protsessor ishlashini o'lchash". ACM aloqalari. 33 (5): 539–543. doi:10.1145/78607.78614.
• Kvinn, Maykl J. (2004). MPI va OpenMP bilan C da parallel dasturlash. Boston: McGraw-Hill. ISBN  0-07-058201-7.

Tashqi havolalar

• Karp-Flatt metrikasi bo'yicha ma'ruza matnlari - Virginia Tech