Aǵımdı qayta islew

Kompyuter iliminde aǵımdı qayta islew (waqıyalar aǵımın qayta islew, maǵlıwmatlar aǵımın qayta islew yamasa bólistirilgen aǵımdı qayta islew dep te ataladı) — bul waqıt boyınsha waqıyalar aǵımların yamasa izbe-izliklerin esaplawdıń oraylıq kirgiziw hám shıǵarıw obyektleri retinde qarastıratuǵın programmalastırıw paradigması. Aǵımdı qayta islew maǵlıwmatlar aǵımın programmalastırıw, reaktiv programmalastırıw hám bólistirilgen maǵlıwmatlardı qayta islewdi óz ishine aladı. Aǵımdı qayta islew sistemaları maǵlıwmat aǵımları ushın parallel qayta islewdi ashıwǵa umtıladı hám nátiyjeli ámelge asırıw ushın aǵım algoritmlerine súyenedi. Bul sistemalar ushın programmalıq támiynat stegi esaplawdı ańlatıw ushın programmalastırıw modelleri hám soraw tilleri sıyaqlı komponentlerdi; bólistiriw hám jobalastırıw ushın aǵım basqarıw sistemaların; hám haqıyqıy san birlikleri, grafikalıq qayta islew birlikleri hám maydanda programmalastırılatuǵın ventil massivleri sıyaqlı tezletiw ushın apparatlıq támiynat komponentlerin óz ishine aladı.

Aǵımdı qayta islew paradigması orınlanıwı múmkin bolǵan parallel esaplawdı sheklew arqalı parallel programmalıq támiynat hám apparatlıq támiynattı ápiwayılastıradı. Maǵlıwmatlar izbe-izligi (aǵım) berilgen bolsa, aǵımdaǵı hárbir elementke bir qatar operaciyalar (yadro funkciyaları) qollanıladı. Yadro funkciyaları ádette konveyerli boladı hám sırtqı yad óz-ara tásiri menen baylanıslı ótkiziw qábiletiniń joytılıwın minimallastırıw ushın optimal lokal chipte yad qayta paydalanıwına urınıladı. Bir yadro funkciyası aǵımdaǵı barlıq elementlerge qollanılatuǵın birdey aǵım ádettegi bolıp tabıladı. Yadro hám aǵım abstrakciyaları maǵlıwmatlarǵa ǵárezliliklerdi ashıp bergenlikten, kompilyator quralları chiptegi basqarıw wazıypaların tolıq avtomatlastıra hám optimallastıra aladı. Aǵımdı qayta islew apparatlıq támiynatı, mısalı, ǵárezlilikler belgili bolǵanda tikkeley yadqa kiriwdi (DMA) baslaw ushın esap taxtasın paydalana aladı. Qol menen DMA basqarıwdıń joq etiliwi programmalıq támiynat quramalılıǵın azaytadı hám baylanıslı apparatlıq támiynat keshlengen kirgiziw/shıǵarıwdıń joq etiliwi arifmetikalıq logika birlikleri sıyaqlı arnawlı esaplaw birlikleri tárepinen xızmet kórsetiliwi kerek bolǵan maǵlıwmatlar aymaǵınıń keńeytiliwin azaytadı.

1980-jıllar dawamında aǵımdı qayta islew maǵlıwmatlar aǵımın programmalastırıw sheńberinde izertlendi. Mısal retinde SISAL (Streams and Iteration in a Single Assignment Language) tilin keltiriwge boladı.

Qollanılıwı

Aǵımlı qayta islew negizinde dástúrli DSP yamasa GPU tipindegi qosımshalar (súwret, video hám cifrlı signaldı qayta islew sıyaqlı) ushın júdá jaqsı isleytuǵın, biraq maǵlıwmatlar bazaları sıyaqlı kóbirek tosınarlı maǵlıwmatlarǵa kiriwi bar ulıwma maqsetli qayta islew ushın onsha emes maǵlıwmatlarǵa baǵdarlanǵan model menen basqarılıp, kompromiss bolıp tabıladı. Modeldegi ayırım qolaylılıqtan qutılıw arqalı, nátiyjeleri ańsatıraq, tezirek hám nátiyjelirek orınlawǵa múmkinshilik beredi. Kontekstke baylanıslı, processor dizaynı maksimal nátiyjelilik ushın sazlanıwı yamasa qolaylılıq ushın kompromiss bolıwı múmkin.

Aǵımdı qayta islew úsh qosımsha ózgesheliklerine iye bolǵan qosımshalar ushın ásirese qolaylı:

• Esaplaw intensivligi, kirgiziw/shıǵarıw yamasa global yadqa bir silteme ushın arifmetikalıq operaciyalar sanı. Búgingi kúnde kóp signal qayta islew qosımshalarında ol 50:1 den asadı hám algoritmlik quramalılıq penen artıp barmaqta.
• Maǵlıwmatlar parallelligi, eger birdey funkciya kirgiziw aǵımınıń barlıq jazıwlarına qollanılsa hám bir qatar jazıwlar aldınǵı jazıwlardan nátiyjelerdi kútpesten bir waqıtta qayta isleniwi múmkin bolsa, yadroda bar boladı.
• Maǵlıwmat lokallıǵı — bul signal hám media qayta islew qosımshalarında keń tarqalǵan waqıtsha lokallıqtıń arnawlı bir túri, bunda maǵlıwmatlar bir ret payda etiledi, qosımshada keyinirek bir yamasa eki ret oqıladı hám basqa heshqashan oqılmaydı. Yadrolar arasında ótkiziletuǵın aralıq aǵımlar, sonday-aq yadro funkciyaları ishindegi aralıq maǵlıwmatlar bul lokallıqtı aǵımdı qayta islew programmalastırıw modelin qollanıp tikkeley uslap alıwı múmkin.

Aǵımlar ishindegi jazıwlarǵa mısallar:

• Grafikada, hárbir jazıw úshmúyeshlik ushın tómengi, normal hám reń informaciyası bolıwı múmkin;
• Súwretti qayta islewde, hárbir jazıw súwretten alınǵan bir piksel bolıwı múmkin;
• Video kodlawshıda, hárbir jazıw maǵlıwmatlardıń bir makroblogın quraytuǵın 256 piksel bolıwı múmkin; yamasa
• Sımsız signallardı qayta islewde, hárbir jazıw antennadan alınǵan úlgilerdiń bir izbe-izligi bolıwı múmkin.

Hárbir jazıw ushın biz tek kirgiziwden oqıy alamız, oǵan operaciyalar orınlay alamız hám shıǵarıwǵa jaza alamız. Bir neshe kirgiziwler hám bir neshe shıǵarıwlarǵa iye bolıwǵa ruqsat etiledi, biraq bir waqıtta oqılatuǵın hám jazılatuǵın yad bólimine hesh qashan iye bola almaymız.

Kod mısalları

Illyustraciya ushın, tómendegi kod bólimleri waqıya aǵımları ishindegi úlgilerdi anıqlawdı kórsetedi. Birinshisi — úziliksiz SQL sorawı (waqıt belgileri hám ayna dawamlılıǵına tiykarlanǵan kelip atırǵan maǵlıwmatlardı sheksiz qayta isleytuǵın soraw) arqalı maǵlıwmat aǵımın qayta islew mısalı. Bul kod bólimi eki maǵlıwmat aǵımınıń, biri akciya buyırtpaları ushın, ekinshisi nátiyjedegi akciya sawdaları ushın, JOIN operaciyasın kórsetedi. Soraw Buyırtpa berilgennen keyin bir sekund ishinde Sawda menen sáykeslestirilgen barlıq Buyırtpalar aǵımın shıǵaradı. Shıǵarıw aǵımı waqıt belgisi boyınsha, bul jaǵdayda Buyırtpalar aǵımınan alınǵan waqıt belgisi boyınsha sortlanǵan.

SELECT DataStream
   Orders.TimeStamp, Orders.orderId, Orders.ticker,
   Orders.amount, Trade.amount
FROM Orders
JOIN Trades OVER (RANGE INTERVAL '1' SECOND FOLLOWING)
ON Orders.orderId = Trades.orderId;

Basqa kod bólegi mısalı shirkew qońırawlarınıń shıńǵırlawı, smoking yamasa kúndizgi kostyumdegi erkektiń payda bolıwı, aqqan aq kóylektegi hayal hám hawada ushıp júrgen gúrish sıyaqlı sırtqı «waqıyalar» aǵımı arasınan toylardı anıqlaydı. «Quramalı» yamasa «kompozit» waqıya — bul jeke ápiwayı waqıyalardan shıǵarılatuǵın nárse: toy bolıp atır.

WHEN Person.Gender EQUALS "man" AND Person.Clothes EQUALS "tuxedo"
FOLLOWED-BY
  Person.Clothes EQUALS "gown" AND
  (Church_Bell OR Rice_Flying)
WITHIN 2 hours
ACTION Wedding

Aldınǵı parallel paradigmalar menen salıstırıw

Tiykarǵı kompyuterler izbe-iz orınlanıw paradigmasınan baslandı. Dástúrli oraylıq processorlar SISD tiykarında, yaǵnıy olar konceptual túrde bir waqıtta tek bir operaciyanı ǵana orınlaydı. Dúnyanıń esaplaw mútájlikleri ósken sayın, basqarılıwı kerek bolǵan maǵlıwmatlar kólemi júdá tez ósti. Izbe-iz programmalastırıw modeliniń artıp atırǵan qayta islew kúshi mútájligin qanaatlandıra almaytuǵını anıq boldı. Úlken kólemdegi esaplawlardı orınlawdıń alternativ jolların tabıw ushın hár túrli háreketler jumsaldı, biraq jalǵız sheshim — belgili bir dárejedegi parallel orınlawdı qollanıw boldı. Bul háreketlerdiń nátiyjesi SIMD boldı, bul bir kórsetpeni (hár túrli) maǵlıwmatlardıń bir neshe instanciyalarına qollanıwǵa imkaniyat beretuǵın programmalastırıw paradigması. Kóbinese, SIMD SWAR ortalıǵında qollanılatuǵın edi. Quramalıraq strukturalardı qollanıw arqalı, MIMD parallelligine de iye bolıwǵa bolatuǵın edi.

Bul eki paradigma nátiyjeli bolǵanına qaramastan, real dúnyadaǵı implementaciyalar yad tegislewi máselelerinen sinxronizaciya máselelerine hám sheklengen parallellikke shekemgi sheklewler menen ushırasqan. Az sanlı SIMD processorları ǵana jeke komponentler retinde saqlanıp qaldı; kópshiligi standart oraylıq processorlarǵa jaylastırıldı.

100 4-komponentli vektorlardan (yaǵnıy, barlıǵı 400 san) ibarat eki massivti qosatuǵın ápiwayı bir programmanı qarastırayıq.

Ádettegi, izbe-iz paradigma

for (int i = 0; i < 400; i++) {
    result[i] = source0[i] + source1[i];
}

Bul eń tanıs izbe-iz paradigma. Ishki cikller, strukturalar hám t.b. sıyaqlı variantlar bar, biraq olar aqıbetinde sol konstrukciyaǵa kelip tireledi.

Parallel SIMD paradigması, paketlengen registrler (SWAR)

// for each vector
for (int elem = 0; elem < 100; elem++) {
    vectorSum(result[elem], source0[elem], source1[elem]);
}

Bul negizinde júdá ápiwayılastırılǵan. Ol vector_sum kórsetpesiniń isleytuǵının esapqa aladı. Bul kórsetpe intrinsikleri menen júz beretuǵın nárse bolsa da, bul jerde vektor komponentleriniń sanı hám olardıń maǵlıwmat formatı sıyaqlı kóp informaciya esapqa alınbaǵan. Bul anıqlıq ushın islengen.

Degen menen, siz bul usıldıń deshifrlanǵan kórsetpeler sanın numElements * componentsPerElement-ten numElements-ke shekem azaytatıǵının kóre alasız. Sekiriw kórsetpeleriniń sanı da kemeydi, sebebi cikl azıraq ret orınlanadı. Bul jeńisler tórt matematikalıq operaciyanıń parallel orınlanıwı nátiyjesinde payda boladı.

Degen menen ne bolǵan bolsa, paketlengen SIMD registri belgili bir muǵdarda maǵlıwmat saqlaydı, sonlıqtan kóbirek parallellik alıw múmkin emes. Tezleniw biraz tórt parallel operaciyanı orınlaw boljawı menen sheklengen (bul AltiVec hám SSE ekewi ushın da keń tarqalǵanın esletip ótemiz).

Parallel aǵım paradigması (SIMD/MIMD)

// This is a fictional language for demonstration purposes.
elements = array streamElement([number, number])[100]
kernel = instance streamKernel("@arg0[@iter]")
result = kernel.invoke(elements)

Bul paradigmada, hárbir komponent blogı bólek anıqlanıw ornına, pútkil maǵlıwmatlar toplamı anıqlanadı. Maǵlıwmatlar toplamın táriyiplew birinshi eki qatarda boladı dep esaplanadı. Sonnan keyin, nátiyje derekler menen yadrodan shıǵarıladı. Ápiwayılıq ushın, kirgiziw hám shıǵarıw maǵlıwmatları arasında 1:1 sáykeslik bar, biraq bul shárt emes. Qollanılatuǵın yadrolar da ádewir quramalı bolıwı múmkin.

Bul paradigmanıń bir implementaciyası cikldi ishki jaqtan «jazıp shıǵa» aladı. Bul ótkiziw qábiletiniń chip quramalılıǵı menen masshtablanıwına imkaniyat beredi, júzlegen ALU-lardı ańsat paydalanadı. Quramalı maǵlıwmat úlgileriniń joq etiliwi bul qosımsha kúsh kóbirek qoljetimli etedi.

Aǵımdı qayta islew SIMD/MIMD qayta islewiniń bir tarmaǵı bolsa da, olardı shatastırmaw kerek. SIMD implementaciyaları kóbinese «aǵım» usılda isley alsa da, olardıń ónimliligi salıstırıwǵa bolmaydı: model óz aldına ádewir úlken ónimlilikke imkaniyat beretuǵın júdá basqasha paydalanıw úlgisin názerde tutadı.

Standart oraylıq processorlar sıyaqlı ulıwma processorlarǵa qollanılǵanda, tek 1.5x tezleniwge erisiwge bolatuǵını atap ótilgen. Kerisinshe, arnawlı aǵım processorları ańsat 10x ten artıq ónimlilikke erisedi, bul tiykarınan nátiyjelirek yadqa kiriw hám joqarı dárejedegi parallel qayta islew menen baylanıslı.

Model tárepinen ruqsat etilgen qolaylılıq dárejeleri hár túrli bolǵanına qaramastan, aǵım processorları ádette yadro yamasa aǵım ólshemine belgili bir sheklewler qoyadı. Mısalı, tutınıwshı apparatlıq támiynatı kóbinese joqarı dálliktegi matematikanı orınlaw imkaniyatına iye emes, quramalı janapay siltemeler shınjırları joq yamasa orınlanıwı múmkin bolǵan kórsetpeler sanına tómenirek sheklewler qoyadı.

Izertlew

Stenford universitetiniń aǵımdı qayta islew joybarlarına 1999-jılı baslanǵan Stanford Real-Time Programmable Shading Project kiredi. Imagine dep atalǵan prototip 2002-jılı islep shıǵıldı. Merrimac dep atalǵan joybar shama menen 2004-jılǵa shekem dawam etti. AT&T sonday-aq grafikalıq qayta islew birlikleri tezlik hám funkcional imkaniyatlar jaǵınan tez rawajlanǵan sayın aǵım menen kúsheytilgen processorlardı izertledi. Usı dáslepki kúnlerden baslap, onlaǵan aǵımdı qayta islew tilleri, sonday-aq arnawlı apparatlıq támiynat islep shıǵıldı.