Kahn processnätverk

Ett Kahn-processnätverk ( KPN eller processnätverk ) är en distribuerad beräkningsmodell där en grupp deterministiska sekventiella processer kommunicerar genom obundna först in, först ut- kanaler. Modellen kräver att läsning från en kanal är blockerande medan skrivning är icke-blockerande . På grund av dessa nyckelrestriktioner uppvisar det resulterande processnätverket deterministiskt beteende som inte beror på beräkningstidpunkten eller på kommunikationsförseningar .

Kahns processnätverk utvecklades ursprungligen för att modellera parallella program, men har visat sig vara praktiska för modellering av inbäddade system , högpresterande datorsystem , signalbehandlingssystem , strömbehandlingssystem , dataflödesprogrammeringsspråk och andra beräkningsuppgifter. KPN introducerades av Gilles Kahn 1974.

Ett Kahn-processnätverk med tre processer (vertices) och tre kommunikationskanaler (edges). Under dess exekvering läser processen P från kanal A och B och skriver till kanal C.

Utförandemodell

KPN är en vanlig modell för att beskriva signalbehandlingssystem där oändliga dataströmmar omvandlas inkrementellt av processer som exekveras i sekvens eller parallellt. Trots parallella processer krävs inte multitasking eller parallellism för att exekvera denna modell.

I en KPN kommunicerar processer via obegränsade FIFO- kanaler. Processer läser och skriver atomära dataelement , alternativt kallade tokens , från och till kanaler. Att skriva till en kanal är icke-blockerande , dvs det lyckas alltid och stoppar inte processen, medan läsning från en kanal är blockerande , dvs en process som läser från en tom kanal kommer att stanna och kan bara fortsätta när kanalen innehåller tillräckligt med dataelement ( polletter ). Processer är inte tillåtna att testa en ingångskanal för förekomst av tokens utan att konsumera dem. En FIFO kan inte konsumeras av flera processer, och inte heller kan flera processer skriva till en enda FIFO. Givet en specifik ingångshistorik (token) för en process måste processen vara deterministisk så att den alltid producerar samma utdata (tokens). Timing eller exekveringsordning för processer får inte påverka resultatet och därför är det förbjudet att testa ingångskanaler för tokens.

Anteckningar om processer

En process behöver inte läsa någon indata eller ha några ingångskanaler eftersom den kan fungera som en ren datakälla
En process behöver inte skriva någon utgång eller ha några utgångskanaler
Att testa ingångskanaler för tomhet (eller icke-blockerande läsningar ) kan tillåtas i optimeringssyfte, men det bör inte påverka utgångar. Det kan vara fördelaktigt och/eller möjligt att göra något i förväg snarare än att vänta på en kanal. Anta till exempel att det fanns två läsningar från olika kanaler. Om den första läsningen skulle stanna (vänta på en token) men den andra läsningen kunde lyckas direkt, kan det vara fördelaktigt att läsa den andra först för att spara tid, eftersom själva läsningen ofta tar lite tid (t.ex. tid för minnesallokering eller kopiering) ).

Processeldningssemantik som Petri-nät

Avfyringssemantik för process P modellerad med ett Petri-nät som visas i bilden ovan

Förutsatt att process P i KPN ovan är konstruerad så att den först läser data från kanal A , sedan kanal B , beräknar något och sedan skriver data till kanal C , kan exekveringsmodellen för processen modelleras med Petri-nätet som visas till höger . Den enda token på PE-resursplatsen förbjuder processen från att exekvera samtidigt för olika indata. När data anländer till kanal A eller B placeras tokens på platserna FIFO A respektive FIFO B. Petri-nätets övergångar är associerade med respektive I/O-operationer och beräkning. När data har skrivits till kanal C , fylls PE-resursen med dess initiala markering igen, vilket tillåter ny data att läsas.

Process som en finita tillståndsmaskin

En ändlig tillståndsmaskin för en process

En process kan modelleras som en finita tillståndsmaskin som är i ett av två tillstånd:

Aktiva; processen beräknar eller skriver data
Vänta; processen är blockerad (väntar) på data

Förutsatt att den finita tillståndsmaskinen läser programelement som är associerade med processen, kan den läsa tre typer av tokens, vilka är "Compute", "Read" och "Write token". Dessutom kan den i Vänta -tillståndet endast återgå till Aktivt läge genom att läsa en speciell "Hämta token" vilket betyder att kommunikationskanalen som är associerad med väntan innehåller läsbar data.

Egenskaper

Avgränsning av kanaler

En kanal är strikt begränsad av $b$ om den har högst $b$ oanvända tokens för eventuell exekvering. En KPN är strikt begränsad av $b$ om alla kanaler är strikt begränsade av $b$ .

Antalet oanvända tokens beror på exekveringsordern ( schemaläggning ) av processer. En spontan datakälla skulle kunna producera godtyckligt många tokens till en kanal om schemaläggaren inte skulle exekvera processer som förbrukar dessa tokens.

En verklig applikation kan inte ha obegränsade FIFO och därför måste schemaläggning och maximal kapacitet för FIFO utformas till en praktisk implementering. Den maximala kapaciteten för FIFO:er kan hanteras på flera sätt:

FIFO-gränser kan härledas matematiskt i design för att undvika FIFO-spill. Detta är dock inte möjligt för alla KPN:er. Det är ett oavgörligt problem att testa om en KPN är strikt begränsad av $b$ . ^{[ citat behövs ]} Dessutom, i praktiska situationer, kan bunden vara databeroende.
FIFO-gränser kan höjas på begäran.
Blockerande skrivningar kan användas så att en process blockerar om en FIFO är full. Detta tillvägagångssätt kan tyvärr leda till ett artificiellt dödläge om inte designern korrekt härleder säkra gränser för FIFO (Parks, 1995). Lokal artificiell detektering vid körning kan vara nödvändig för att garantera produktionen av korrekt utdata.

Slutna och öppna system

En sluten KPN har inga externa in- eller utgångskanaler. Processer som inte har några ingångskanaler fungerar som datakällor och processer som inte har några utkanaler fungerar som datasänkor. I en öppen KPN har varje process minst en ingångs- och utgångskanal.

Determinism

Processer för en KPN är deterministiska . För samma ingångshistorik måste de alltid producera exakt samma utdata. Processer kan modelleras som sekventiella program som läser och skriver till portar i valfri ordning eller kvantitet så länge som determinismegenskapen bevaras. Som en konsekvens är KPN-modellen deterministisk så att följande faktorer helt och hållet bestämmer utdata från systemet:

processer
nätverket
initiala tokens

Tidpunkten för processerna påverkar därför inte systemets utdata.

Monotonicitet

KPN-processer är monotona . Att läsa fler tokens kan bara leda till att man skriver fler tokens. Tokens som läses i framtiden kan bara påverka tokens som skrivs i framtiden. I en KPN finns en total ordning av händelser ^{[ förtydligande behövs ]} inuti en signal. ^{[ förtydligande behövs ]} Det finns dock ingen ordningsrelation mellan händelser i olika signaler. Således är KPN:er endast delvis beställda, vilket klassificerar dem som en otidsbestämd modell.

Ansökningar

På grund av dess höga uttrycksförmåga och kortfattade, används KPN:er som underliggande beräkningsmodell i flera akademiska modelleringsverktyg för att representera strömningsapplikationer, som har vissa egenskaper (t.ex. dataflödesorienterade, strömbaserade).

Daedalus-ramverket med öppen källkod som underhålls av Leiden Embedded Research Center vid Leiden University accepterar sekventiella program skrivna i C och genererar en motsvarande KPN. Denna KPN skulle till exempel kunna användas för att systematiskt mappa KPN på en FPGA -baserad plattform.

Ambric Am2045 massivt parallella processorer är en KPN implementerad i faktiskt kisel . Dess 336 32-bitars processorer är anslutna via en programmerbar sammankoppling av dedikerade FIFO:er. Sålunda är dess kanaler strikt begränsade till blockerande skrivningar.

Se även

Vidare läsning

Lee, EA; Parks, TM (1995). "Dataflödesprocessnätverk" (PDF) . IEEE:s förfaranden . 83 (5): 773–801. doi : 10.1109/5.381846 . ISSN 0018-9219 . Hämtad 2019-02-13 .
Josephs, Mark B. (2005). "Modeller för dataflödessekventiella processer". I Abdallah, Ali E.; Jones, Cliff B.; Sanders, Jeff W. (red.). Kommunicera sekventiella processer. The First 25 Years: Symposium on the Occasion of 25 Years of CSP, London, Storbritannien, 7-8 juli 2004. Revided Invited Papers . Föreläsningsanteckningar i datavetenskap. Vol. 3525. Berlin, Heidelberg: Springer Berlin Heidelberg. s. 85–97. CiteSeerX 10.1.1.60.5694 . doi : 10.1007/11423348_6 . ISBN 978-3-540-32265-8 .