Sammanfattning Resultaten tyder på att iScheduling kan förbättra både väntetid och total svängtid avsevärt för dessa arbetsbelastning klasser, överträffa standard policys såsom backfilling och formbara jobb schemaläggning. Att effektivt genomföra resursintensiva parallella vetenskapliga tillämpningar i dynamiska parallella och distribuerade produktionsmiljöer är ett utmanande problem. Prestanda beror på resursplanering på flera nivåer: jobbplanerare som multiplicerar olika applikationer med begränsade systemresurser och programplanerare som begär resurser för sina tillämpningar. Applikationer kan uppleva stora avmattningar i tidsdelade system, eller höga väntetider i rymddelade system, på grund av argument för dessa begränsade värdefulla resurser. En del av problemet är att en begränsad uppsättning delade resurser snabbt kan bli 2 övertecknade eftersom antalet ansökningar för att köra ökningar. Detta bekräftas av flera studier av superdatorns arbetsbelastning [10] [11] [20]. Vi anser dock att ineffektiv resursfördelning genom arbetsplanerare och ineffektiv resursanvändning i ansökan ytterligare förvärrar detta problem. Problemet är att arbetsschemaläggare för parallella maskiner ofta byggs för att optimera mätvärden som kanske inte ger bästa möjliga applikationsprestanda. Till exempel, många jobb schemaläggning politik är inriktade på högt resursutnyttjande eftersom stora parallella maskiner är dyra, eller rättvisa (t.ex. först till kvarn), eller hög genomströmning. Dessutom är arbetsschemaläggningen statisk: Arbetsschemaläggare för parallella tillämpningar omprövar i allmänhet inte tidigare beslut om schemaläggning. Ett annat problem är att jobbplanering kan få minimalt stöd i distribuerade nätverksmiljöer. Utan samordning kommer olika programplanerare att fatta oberoende planeringsbeslut som kan leda till minskad tillämpning och systemprestanda. Osamordnade programplanerare kan också stöta på rasförhållanden på delade resurser. Dessutom väljer programplanerare vanligtvis resurser utan hänsyn till den negativa inverkan detta kan ha på andra program. I vissa fall kan programplanerare till och med överallokera resurser med begränsad nytta av deras tillämpning. Detta gäller särskilt när slutanvändaren utför programplanering eftersom det kan vara svårt att manuellt bestämma lämpligt antal resurser för applikationer med en hög grad av varians eller databeroende beteende. Vi anser att bristen på prestanda som levereras till ansökningar delvis beror på den funktionella klyftan mellan programplanering och jobbplanering. Programplanerare fattar beslut om resursfördelning enbart för sin ansökan [3] [32] [33]. De utnyttjar specifik kunskap om applikationen för att välja resurser som förväntas ge resultat som uppfyller användarnas mål såsom minimal respons eller slutförandetid. Däremot har arbetsschemaläggningen en mer global syn och fattar beslut om resursfördelning över en uppsättning arbetstillfällen [5] [9] [13] [15] [21]. Arbetsschemaläggningen spänner över fördelningspolicyer för tidsdelningspolicyer för kombinerade tillvägagångssätt [35]. Varje parallell applikation antas vara en svart låda med liten eller ingen medföljande information. I detta dokument föreslår vi en ny integrerad planeringsram (iScheduler) som överbryggar klyftan mellan tillämpning och arbetsplanering för parallella vetenskapliga tillämpningar. Vi antar att jobbet eller applikationen redan har brutits ned i en parallell beräkning och att den har ett speciellt front-end (kallas adaptiv API) som kommer att beskrivas inom kort. Den vanligaste modellen för iSchedulerjobb är dataparallell där de parallella komponenterna är identiska, även om detta inte är ett strikt krav. IScheduler är en program-medveten jobb schemaläggare i motsats till en allmän-purpose system schemaläggare. Application-aware innebär att jobb schemaläggaren kan interagera med jobben som de kör. Den styr dynamiskt resursfördelningen bland en uppsättning konkurrerande applikationer, men till skillnad från en traditionell jobbschemaläggare kan den interagera direkt med en applikation under genomförandet för att optimera resurstilldelningen. I vissa fall kan den utnyttja 3 tillämpningsspecifika kunskaper, t.ex. Det kan använda beräknad genomförandetid, och i andra gör det mer allmänna beslut. Application-awareness uppnås via adaptiv API. IScheduler kan användas på två sätt. En användarcentrerad iScheduler kan mer effektivt hantera en pool av resurser (t.ex. en partition av en superdator eller ett kluster) för en uppsättning relaterade program som lämnas in av en enda användare. Till exempel, många problem kräver upprepade utförande av samma eller liknande tillämpningar såsom parameterstudier, monte-carlo modeller, och gensekvens jämförelse, där resultaten från varje körning är normalt medelvärden för ett slutresultat, eller inmatning i efterföljande körningar, eller helt enkelt samlas in som delar av den övergripande lösningen. Arbetsbelastningsspår från superdatorloggar avslöjar en hög grad av applikationsrepetition [30] och detta har bekräftats av flera informella undersökningar [8] och anonymiserade arbetsbelastningsspår [11]. En systemcentrerad iScheduler fungerar över en uppsättning gemensamma ansökningar som lämnas in av olika användare. Till exempel kan domänspecifika problemlösningsmiljöer (PSE) [2] [6] [19] [22] [27] använda iScheduler för att hantera resurstilldelningen i samband med varje samtidig begäran (t.ex. för att lösa ett ekvationssystem) som lagts fram för en PSE. Vi har utvecklat ett iScheduler ramverk och tillämpat det både på en superdator arbetsbelastning som härrör från spårdata på flera centra och på en ström av verkliga parallella jobb som vi har genomfört. Resultaten tyder på att den integrerade schemaläggningen förbättrade både väntetiden och sluttiden för parallella tillämpningar jämfört med flera grundläggande schemaläggningspolicyer, inklusive återfyllning och formbar schemaläggning av jobb, men över en storleksordningsförbättring jämfört med standardschemaläggningspolicyn. IScheduler IScheduler är en program-medveten jobb schemaläggare som är utformad för att utnyttja fördelarna med program- och jobbnivå schemaläggning. Traditionell arbetsschemaläggning är statisk: jobb schemaläggare för parallella applikationer i allmänhet inte ompröva tidigare schemaläggning beslut. graden av interaktion mellan en jobb schemaläggare och ansökan (eller dess schemaläggare) är minimal och vanligtvis består av en inledande resurs begäran (t.ex. Jobbet vill ha P-processorer). Dessutom, om den ursprungliga resursbegäran inte kan tillgodoses, måste ansökan vänta eftersom det ofta inte finns någon mekanism för att göra det möjligt för den att skaffa resurser senare, även om den skulle kunna börja med färre resurser. Slutligen, om vissa av de resurser som finns i en ansökan behövs av en högre prioritet ansökan, då jobb schemaläggaren har inget annat val än att avbryta hela ansökan. IScheduler utför flytande resurshantering för ett program (liksom en program-nivå schemaläggare), men kommer att utföra resurshantering över en jobbström (som en jobbnivå schemaläggare). En sådan integration är inte gratis. Det kräver ett API som ger applikationsinformation (sensing) och 4 förmåga att kontrollera programmets beteende (actimera). Sensing ger dynamisk prestandainformation såsom per iteration genomförandekostnad, medan aktivering används för att vidta åtgärder på ansökan, t.ex. lägga till eller ta bort processorer till det. Integrerad schemaläggning kräver att ansökan ändras för att stödja dessa avkännings- och aktiveringsfunktioner. IScheduler fattar schemaläggningsbeslut för en potentiellt dynamisk samling av applikationsärenden över en resurspool, t.ex. Ett kluster, en parallell superdator, ett nätverk av kluster eller ett datoriserat rutnät. Det fungerar i samförstånd med programplanerare för att fatta effektiva resursfördelningsbeslut både statiskt och dynamiskt (figur 1 ). I detta dokument är den resurs som vi fokuserar på processorer. Till skillnad från traditionella schemaläggningsmetoder är resurshantering i iScheduler en flytande process där resurser kan fördelas och fördelas under en applikations hela livstid. iScheduler resurshantering bygger på tre kärnidéer: • kostnadsprognoser • anpassningsförmåga Figur 1: iScheduler arkitektur. iScheduler hanterar inkommande programström (visas som ett program A i och dess schemaläggare AS i ) och fördelar resurser över 16 processorer. Vi har visat programschemaläggaren som frikopplad från ansökan, men i vissa fall kan programschemaläggaren vara inbäddad i ansökan. Användning resurskrav (om kända) och begränsningar kan tillhandahållas -min är den nödvändiga minsta mängden resurs och ideal är den önskade mängden. Det finns två aktiva ansökningar (A 1, A 2 ) och två köade ansökningar (A 3, A 4 ). Application A 1 har gjort en dynamisk begäran om ytterligare 2 Processorer. iScheduler fattar tilldelningsbeslut med hjälp av information från alla avbildade källor. Kostnadsförutsägelsemodeller gör det möjligt för iScheduler att utvärdera och tilldela kandidatresurser till sin kollektiva uppsättning ansökningar på ett sätt som uppfyller prestationsmålen. Det gör det möjligt för iScheduler att bedöma kostnaderna för och fördelarna med fördelning av resurser och beslut om tilldelning av resurser. Adaptivitet gör det möjligt för applikationen och iScheduler att justera sitt beteende som svar på dynamiska run-time händelser. Det ger iScheduler större flexibilitet när det gäller att fatta beslut om kollektiv resursfördelning. Antagningskontroll är ett beslut som fattas när en ny ansökan kommer till systemet. IScheduler måste bestämma om ansökan ska köas eller köras genom att släppa in den i systemet. Detta är särskilt viktigt när systemresurser övertecknas med avseende på applikationsströmmen. När en ansökan beviljas måste iScheduler se till att det finns tillräckliga resurser för ansökan. Detta kan kräva att iScheduler tar bort resurser från att köra program. Anta till exempel att ett parallellt system innehåller 128 rumsdelade processorer och att en parallell applikation körs på 120 processorer. Med hjälp av traditionella jobb schemaläggare, en ny anlända ansökan som kräver 16 processorer skulle köas (om inte den nya ansökan hade högre prioritet). Med hjälp av en formbar jobbplanering, skulle det nya jobbet kunna ges de 8 fria processorer som sannolikt skulle resultera i dålig prestanda. Däremot kunde iScheduler dra 8 ytterligare processorer från den första applikationen kanske inte påverkar dess körtid i någon större utsträckning, vilket skulle göra det möjligt för den nya applikationen att köra. Observera också hur detta förbättrar maskinutnyttjandet i förhållande till traditionell arbetsplanering eftersom de 8 processorer inte längre är sysslolösa. I många fall finns det en punkt med att minska avkastningen när det gäller mängden resurser för många tillämpningsklasser, så straffet för att ta bort resurser kanske inte är betydande (se figur 2 för några exempel). IScheduler fattar resurshanteringsbeslut som en funktion av prediktiva kostnadsfunktioner C, aktiva applikationer AA (inklusive deras prioritet, prestandahistorik, ålder, nuvarande resurstilldelningar och begränsningar, och eventuella pågående resursförfrågningar), köade program QA (inklusive deras prioritet, väntetid, resursbehov och begränsningar), och tillgängliga resurser AR. Utrymmet för iScheduling dec- Figur 2: Punkt av minskande avkastning för a) data parallell, b) master-slave bag-of-tasks, och c) pipeline applikationer (N är problemstorleken, P # processorer). I a) och b), en parabolisk form ses ofta. I a) kurvan vänder uppåt när kommunikationen börjar kompensera eventuella vinster från parallellism. Konstanterna beror på problem och nätverksparametrar. På samma sätt för b) kurvan dyker upp när de overhead erfarenhet av befälhavaren börjar dominera eventuella vinster. Slutligen för c), anta att varje steg kan köras i T i tid seriellt, och den mittersta scenen är parallell. När T 1 eller T 3 överstiger T 2 /P finns det ingen fördel med att lägga till fler processorer i mitten.  Vi har utvecklat flera policyer för användar- och systemcentrerade iSchedulers som space-share bearbetningsresurser med målet att minska slutförandet tid. Dessa iSchedulers vi har utvecklat gör resursfördelning beslut när ansökningar anländer och slutföra. Den resurs som hanteras är antalet processorer. policyer för iScheduler fluid resurshantering kommer att justera resursförbrukningen för både anländande och körande program. Denna politik kommer till stånd när det inte finns tillräckliga resurser för att ge alla tillämpningar samtidig tillgång till sina ideala resurser. När en ansökan kommer till systemet måste iScheduler avgöra om den ska föras in i systemet. Om den inte kan få sina ideala resurser kan en iScheduler välja att "bärga" resurser från att köra program för att göra det möjligt för den att köra. Skörden består i sig själv av flera frågor: när ska man skörda? från vem att skörda (offren)? och hur mycket att skörda? I det här dokumentet ställer vi in skördeparametern till den minsta resursmängd (min) som programmet behöver. Om resursbeloppet inte kan samlas in måste programmet köas. En ansökan kan inte skördas under dess minimikrav på resurser. När ett program avslutas måste iScheduler bestämma hur tillgängliga resurser ska fördelas till både köade och eventuellt körda program. Om att minimera väntetiden önskas, då bör företräde ges till köade program som ökar graden av parallella jobb multiprogrammering. iScheduler resurshanteringspolicy har fyra komponenter: control_policy, entry_policy, sherp_policy och distribution_policy. Kontroll_policyn hänvisar till globala egenskaper som alla policyer måste respektera. Till exempel, för stabilitet kanske vi vill begränsa hur många gånger en ansökan kan skördas, eller skydda nyanlända ansökningar från skörd tills de når en viss ålder, eller för att säkerställa att nyttan av en adaptiv åtgärd uppväger dess kostnader, etc. Skördepolicyn avgör den drabbade och det belopp som varje ansökan måste avstå från. Distribution_policyn bestämmer vad du ska göra med de resurser som frigörs när en ansökan avslutas. I detta dokument säkerställer alla distributionspolicyer först att antagningspolicyn är nöjd. I det stora utrymmet för möjliga policyer, undersöker vi denna uppsättning av alternativ: 7 antagningskontroll politik uppnå_mp (M): denna politik kommer att tillåta ansökningar i systemet FCFS för att uppnå en grad av multiprogrammering minst lika med M. En ansökan kommer att köas om M har nåtts och otillräckliga fria resurser finns tillgängliga. aldrig_harvest: inte skörda (men omfördelning till löpande program är tillåtet) ens_harvest: denna policy kommer att försöka skörda resurser jämnt från alla löpande program vid varje skörd begäran, oavsett tidigare skördehändelser. Bearbetningsföretagen tas sedan från varje ansökan (en gång i taget) på ett round-robin-sätt tills den skördade tilldelningen är nöjd. Denna politik försöker bara vara rättvis inom en enda skördehändelse. Fair_harvest: Denna politik är en förlängning av even_harvest och försöker utvidga skördepolitiken över flera skördehändelser. Denna politik försöker att hålla antalet skördehändelser som upplevts av alla löpande applikationer på samma nivå. Det gör detta genom att först beräkna det genomsnittliga antalet skördehändelser som de löpande applikationerna drabbas av. Endast de ansökningar som ligger under detta genomsnitt är kandidater för offentliggörande. long_harvest: denna policy order applikationer med sin nuvarande körlängd (längst först). Bearbetningsföretagen tas sedan från varje ansökan (en gång i taget) på ett round-robin-sätt tills den skördade tilldelningen är nöjd. Endast de ansökningar som har en ålder > T-tidsenheter är kandidatoffer. T kan definieras som genomsnittsåldern för alla program som körs. short_harvest 1 : denna policy order applikationer med den mängd körtid som återstår (största först). Bearbetningsföretagen tas sedan från varje ansökan (en gång i taget) på ett round-robin-sätt tills den skördade tilldelningen är nöjd. Endast ansökningar med en tid kvar > T-tidsenheter är kandidatoffer. T kan definieras som den genomsnittliga tiden som återstår av alla program som körs. low_impact_harvest: Denna politik kommer att försöka skörda från de tillämpningar som förväntas påverkas minst. Effekterna bestäms av den andel resurser som en ansökan kommer att ha i förhållande till det önskade idealbeloppet. Till exempel kommer en ansökan som har 2 resurser fördelade med sina idealiska resurser = 4 att få mycket större effekt om en resurs togs bort än en ansökan med 8 resurser fördelade med sina idealiska resurser = 9 (1/4 vs 7/9). Applikationerna beställs av impact metrisk och resurser väljs med hjälp av denna beställning. favor_running: Denna policy kommer att fördela resurser till att köra applikationer med omvänd skördepolitik. Till exempel, om low_impact_harvest valdes, kommer denna politik att omfördelas till program som skulle vara de mest gynnsamt påverkade. favor_queued: denna policy kommer att fördela resurser till köade program för att släppa in dem i systemet först. I detta dokument, de iScheduler policy alternativ vi har undersökt är även_harvest och low_impact_harvest med favor_löpning och favor_queued alternativ för olika värden av M. Vi kallar dessa policys, Even-H-FR, Even-H-FQ, Low-Imp-FR, och Low-Imp-FQ. Den allmänna iScheduler logik och ett exempel på 1. Denna policy kanske inte är genomförbar för alla tillämpningar eftersom den tid som återstår kanske inte är känd. För vissa parallella tillämpningar (t.ex. Direktlösare) kan denna information vara känd. I andra fall kan historisk information om drifttid eventuellt användas. Detta blir möjligt för iSchedulers som schemalägger parallella arbetsströmmar av samma typ och kan samla in och utnyttja denna information online. 8 Even-H-FQ heuristic visas (Figur 3). Vi jämförde dessa iScheduler-strategier med tre baslinjer. Baslinjerna tillåter inte någon ändring av mängden resurser som innehas av körande program: Policy IDEAL-ONLY (ingen anpassning på körande program eller anländande program): anländande ansökan ges sina idealiska resurser; om ideal inte är tillgänglig, ansökan köas med hjälp av FCFS. Policy MOLDABLE (ingen anpassning på körande applikationer): anländande ansökan ges max (min, ideal) resurser; om min inte är tillgänglig, ansökan köas med FCFS. IDEAL-BACKFILL. Backfilling kommer att användas för att slappna av FCFS om köhoppning inte försenar program. Varje ansökan beviljas sina idealiska resurser. iScheduler-aware program måste stödja ett adaptivt API för att göra det möjligt för iSchedulers att genomföra flytande resurshanteringspolicyer. Annars finns inga andra särskilda krav för applikationer: de med skuggade cirkel och har (min, ideal) processor krav. Jobs J 1 och J 2 anländer först till den sysslolösa maskinen och tilldelas sina ideala resurser var (1). Senare (2) anländer J 3 med ett minkrav på 4, men inga resurser finns tillgängliga. Under Even-H skördas 2 resurser från J 1 och J 2 så att J 3 kan köras. Efter detta kommer J 4 också med en min på 4 men måste köas eftersom det inte är möjligt att skörda 4 resurser utan att stänga av de andra jobben. Slutligen i (3) jobb J 3 avslutar frigöra 4 resurser. Med hjälp av FQ ges dessa resurser till det köade jobbet J 4. (1) (2) 9 kan använda trådar, meddelandepass, etc. Applikationer antas ha en körlängd som gör iScheduling lönsamt (minuter eller timmar i stället för några sekunder). Följaktligen antas de vara iterativa, med inledda anpassningshändelser och insamlad kostnadsinformation, vid iterationsgränserna. IScheduler kommer att utvärdera kostnaderna för och fördelarna med adaptiva åtgärder som en del av sina planeringsbeslut. Det är uppenbart att anpassningen inom ramen för ansökan innebär att den måste vara formbar när det gäller systemresurser. Alla tillämpningar kan inte uppfylla detta krav och skulle därför inte vara lämpliga för iScheduling. Många parallella vetenskapliga tillämpningar kan dock skrivas eller modifieras för att fungera på detta sätt. I en nyligen genomförd undersökning rapporterades att minst 70 % av superdatorjobben kunde vara formbara [7]. En viktig fråga är: varför skulle en applikationsskrivare anstränga sig för att genomföra anpassningsförmågan, särskilt avlägsnandet av resurser? Den första punkten att betona är att tillhandahållandet av resurs frigörande faktiskt kan gynna (eller åtminstone inte skada) genomförandet av ansökan. Det finns minst fyra skäl till att resursutgivning kan vara fördelaktigt: (1) resursutsättning kan förhindra att programmet avbryts på grund av förekomsten av högre prioriterade jobb eller en resursägare som återvinner resurser, (2) resursutsättning kan inte skada prestanda på knät av prestandakurvan (figur 2 ), (3) bättre resurser kan bli tillgängliga dynamiskt och svagare resurser skulle kunna frigöras, och (4) Ett annat argument att göra är att om programmeraren är villig att anstränga sig för att få resurser dynamiskt läggas till deras tillämpning (en tydlig fördel i många fall), då kan samma anpassningskod lätt omvandlas för att tillåta resursutgivning eftersom frågor som rör omfördelning av data, kommunikation, belastning ombalansering, är samma i båda fallen. Vi har delat upp adaptiv API i två komponenter, avkänning och aktivering. Funktionen för resursanalys ger information som kan hjälpa iScheduler att fatta beslut om resursfördelning. Minimivärdet är särskilt viktigt eftersom det fungerar som ett hinder för resurstilldelning: ansökan måste ha minst det lägsta belopp som ska köras. Den idealiska mängden är en antydan och krävs inte, även om vissa program schemaläggare kan vara tillgängliga för att ge exakta värden för det. Det kan t.ex. bestämmas utifrån avkänningsfunktionerna för regelbundna dataparallella tillämpningar som kommer att visas. Aktivering funktioner används för att justera resursförbrukningen av applikationer till stöd för flytande resurshantering. Sensing ger användbar information till iScheduler som kan användas i aktiveringsprocessen. Till exempel kan iScheduler använda dynamisk avkänningsinformation för att justera eller justera schemaläggningsbeslut. Aktiveringsfunktionerna är följande: actifying_cost_ benefits (adaptation_ method, num_procs, & cost, & benefits) IScheduler åberopar dessa funktioner inom programmet för att kontrollera sin resursanvändning. Den kan till exempel försöka ta bort processorer från en ansökan för att ge dem till en annan, kanske nyligen anländande ansökan. Det kan också göra det möjligt för en ansökan att få ytterligare bearbetningsföretag när de blir tillgängliga, t.ex. när en ansökan avslutas. Dessa funktioner utgör grundläggande mekanismer för resursanpassning inom applikationen. Hur dessa funktioner används är ett policybeslut som fattas av iScheduler. Förutsäga kostnaden och nyttan av anpassning till ansökan är en viktig ingrediens för att bygga effektiva iSchedulers. Denna information exporteras till iScheduler. Prestandaförutsägelse är grundläggande för applikationsmodell, iScheduler, och adaptiv API. Det besvarar frågorna: hur kommer ansökan att fungera på en given uppsättning resurser och vilka är kostnadsfördelarna med anpassning till stöd för flytande resursförvaltning? I tidigare forskning, har vi haft framgång förutsäga prestanda för tre modeller som är gemensamma för parallella vetenskapliga tillämpningar som använder meddelande-passing: SPMD data parallell, rörledningar, och master-slav bag-of-tasks med hjälp av profeten systemet [32]. Profeten schemalägger parallella tillämpningar med målet att minska slutförandet tid. Det har framgångsrikt applicerats på ett brett spektrum av applikationer inklusive parallell gensekvensjämförelse, elektromagnetisk spridning med hjälp av finita element, och bildbehandling rörledningar. Profeten förutsäger det optimala antalet processorer för en given parallell tillämpning genom att konstruera kostnadsfunktioner som förutsäger applikationens prestanda. Det utforskar en sekvens av processor konfigurationer för att hitta knät på kurvan (Figur 2 ). Profeten ändrades för att exportera intern kostnadsinformation till iScheduler. Denna kostnadsinformation omfattar ansökningsresultat för en uppsättning resurser för en kandidat och det minsta antal resurser som krävs. Dessutom innehåller profeten också modeller som exakt förutsäger kostnaden och nyttan av att lägga till, ta bort, migrera och dynamiskt lasta balansprocessorer [34]. Förutsägelsemodellen uppnådde hög noggrannhet för både kostnader och fördelar med anpassning: inom 10 % för ett stort antal tillämpningar. De två senare anpassningsmetoderna (migration och dynamisk belastningsbalansering) kommer att vara särskilt användbara när miljön innehåller icke-iScheduler-medvetna tillämpningar, ett ämne för framtida undersökningar. I Prophet, de kostnadsmodeller den konstruerar förlitar sig på information som tillhandahålls av ansökan i form av För andra applikationer såsom gängad-parallell, formuleringen är annorlunda. Noggrannheten i Profetens kostnadsmodeller är i allmänhet hög även för komplexa flerfas applikationer. Denna uppringningsinformation används 2. Kommunikationsfunktionen som visas är för ett gemensamt 10-base-Teternet-nätverk där bandbredden delas mellan p-kommunikationsprocessorerna (därav beroendet av p). I en delad miljö beror kostnaden för kommunikation och beräkning på mängden tillgänglig bandbredd som CPU-cyklerna respektive. för att stödja adaptiv API. Till exempel används för att genomföra exec_time-funktionen som en del av avkännande API. Denna information används också för att fastställa kostnader och fördelar med anpassning. Fortsätta med data parallellt exempel, fördelen med att lägga till en processor kan bestämmas genom att ansluta p+1 i ekvationerna ovan. Kostnaden för att lägga till en processor är mer komplex, men bestäms delvis av kostnaden för datakommunikation. Detta kan beräknas med hjälp av en kommunikationskostnadsfunktion (t.ex. men med comm_complexity ersättas med mängden data som ska omfördelas). Anpassningskostnadens modell bygger på andra parametrar som inte visas här och utelämnas för korthet, uppgifter kan hittas i [34]. Vi har använt Prophet callbacks för att implementera en del av avkänningsfunktionen till stöd för adaptiv API. Dessutom tillhandahålls resursbehoven i applikationen också genom callbacks. Till exempel, min_krav rapporterar de min resurser som behövs och de idealiska resurserna kan fastställas internt inom profeten via dess schemaläggning algoritmer. Båda dessa returneras av resursanalysfunktionen till iScheduler. Detta behandlas som en antydan till iScheduler eftersom alla program schemaläggare inte kommer att kunna ge exakt denna information. Profeten integration visade att befintliga schemaläggare kan införlivas i iScheduler ram med minimal svårighet. För att utvärdera potentialen i iScheduler-paradigmet har vi byggt ett iScheduler-ramverk och använt det för att konstruera flera användarcentrerade och systemcentrerade iSchedulers som båda utvärderades genom simulering. Ramverket används för närvarande som en del av en "live" schemaläggare för parallella profetjobb på klusternätverk. Här rapporterar vi resultat om simuleringsförsöken. De användarcentrerade iSchedulers tillämpades för att schemalägga en ström av parallella jobb som lämnats in från en enda användare och använda profet schemaläggningssystemet internt för att generera kostnadsinformation som behövs för den spårdrivna simuleringen. Dessa jobb drevs inledningsvis på vår lilla kluster (ett ATM kluster av 8 Sparc 20 noder) för att generera verklig kostnadsinformation. Simulering gör att vi kan "köra på" större kluster (t.ex. minst 64 noder) med större problemstorlekar för att producera Vi byggde användarcentrerade iSchedulers för tre parallella dataapplikationer, en iterativ jakobilösare (STEN), gaussian eliminering med partiell pivoting (GE), och parallell gensekvensjämförelse (CL), detaljerna i dessa applikationer beskrivs någon annanstans [32]. Dessa tillämpningar ändrades för att fungera med iScheduler (dvs. De genomför adaptiv API) och representerar en användbar inledande test av tillämpligheten av paradigmet: tillämpningarna var inte master-slave, men meddelande-passing program. I synnerhet CL är en riktig tillämpning. Arbetsbördan bestod av fall av varje ansökan med olika problemstorlekar och längder, vilket kan förväntas i en grupp inlämnade jobb. Detta scenario skulle vara lämpligt för en relaterad uppsättning parallella arbetstillfällen som lämnats in av en användare eller den arbetsbörda som begärts av en PSE som erbjöd fasta parallella tjänster [6] [22]. I superdator arbetsbelastning spår vi undersökt, jobb som lämnats in från samma användare i allmänhet föll i tre kategorier: parti eller samtidig inlämning, en-jobb-i-tid inlämning, och överlappande inlämning. Vi modellerade vart och ett av dessa fall genom att justera interarrivalhastigheten av applikationsinstanserna (P är det totala antalet processorer, är den genomsnittliga körtiden för alla applikationsinstanser med tanke på deras ideala antal processorer, är det genomsnittliga ideala antalet processorer för alla applikationsinstanser, och β är en konstant): Värdena för och bestämdes av profeten.  och CL är lika sannolika. På vårt Sparc kluster som kör 100 Mb ethernet, bestämde vi också kostnaden för leverans M byte av data till cirka: 1 +.00009M. För en adaptiv händelse (antingen lägga till eller ta bort) skickas data först till en masterprocessor och sedan vidaredistribueras. Mängden data (M) som flyttas är följande: STEN: 2N 2 *8/P, GE: 2N 2 *8/P, och CL: 2NumSourceSeqs*SeqBlockSize/P Till exempel skulle omkostnaderna för att ta bort en processor för STEN med N=128 vid P=4 vara ungefär 7 sek jämfört med 1289 sek av körningstid. Kostnaden för att lägga till är lite högre eftersom processskapande behövs, men detta är några hundra millisekunder i värsta fall. En fråga för framtida utredning är frågan om hur iScheduling kommer att skalas till stora, möjligen flerfas applikationer som kan vara dynamiska eller oregelbundna i struktur. Det finns inget inom paradigmet när det gäller mekanismen som utesluter utvidgning till större tillämpningar, men det är troligt att det kommer att behövas en ny iScheduling-politik. Till exempel är det möjligt att olika iScheduling policys kan krävas för olika faser av ansökan. Förmågan att lägga till och frigöra resurser kommer att vara särskilt användbar för tillämpningar med olika resursbehov i olika faser. För felaktiga databeroende tillämpningar kan det minsta och idealiska antalet resurser också vara databeroende. Eftersom dessa värden tillhandahålls av resursanalysfunktionen kan denna funktion programmeras till att vara returvärden baserade på indata. Vi byggde en systemcentrerad iScheduler och använde superdatorcenter spår från SDSC IBM SP2 (128 noder), LANL SGI Origin 2000 (2048 noder) och CTC IBM SP2 (512 noder) för att generera arbetsbelastning [11]. Vår modell genererar syntetiska jobb spår genom att modellera statistiken över dessa publicerade spår i termer av jobb interarrival tider, jobbstorlek, och jobb kör tider. Vi observerade att för interarrival, fler jobb anländer till RT ideal =244800 sec 15 systemet under dagen än under natten ( Figur 5). För att fånga upp skillnaderna i ankomstpriserna använde vi en icke-stationär poissonprocess för att modellera de jobb interarrivaltider där ankomsthastigheten λ är en funktion av tiden. De interarrival tiderna genereras från en exponentiell fördelning, vars medelvärde, 1/λ, varierar beroende på (simulerad) tid på dagen ( Figur 6 ). X-axeln representerar de behållare i vilka interarrivaltiderna placeras. Varje behållare är 500 sekunder lång. De flesta av de interarrival tiderna faller i den första soptunnan, vilket tyder på att de flesta jobb anländer inom 500 sekunder från föregående jobb. Även om passformen inte är perfekt, fångar den den första spiken och svans-off effekt. För vår arbetsbörda modell, är storleken på ett jobb kännetecknas av det antal processorer som den begär. I själva arbetsbelastningen spår, det finns några jobbstorlekar som är mycket vanliga. De gemensamma jobbstorlekarna är 1, och makt-av-två storlekar 2, 4, 8, 16, 32 och 64. Alla andra jobbstorlekar förekommer sällan. För våra simulerade arbetsbelastningar använder vi en diskret sannolikhetsfördelning som speglar jobbstorleken i en faktisk arbetsbelastning (figur 7 ). Jobb körtider har modellerats av en Weibull distribution (Figur 8 ). Figuren visar en histogram av alla jobb kör gånger från SDSC arbetsbelastning ritas mot Weibull distribution. Precis som histogrammen för interarrivaltiderna är storleken 500 sekunder. De flesta arbetstillfällen har korta perioder, medan några få arbetstillfällen löper under mycket långa perioder. Vi använder en enda Weibull distribution med uppskattad form parameter α och skala parameter β för att modellera jobbkörningstider för våra simulerade arbetsbelastningar. Varje genererat jobb i spår har en ankomsttid (Figur 6 ), ett idealiskt antal processorer (Figur 7 ), och en genomförandetid med tanke på dess ideala antal processorer (Figur 8 ). För varje ansökan i ett spår vet vi hur lång tid det kommer att ta förutsatt att den ges sina ideala eller önskade resurser. Vi antar att dessa värden är tillgängliga i spåren via figur 8 eller tabell 1. För flera schemaläggningspolicyer, bl.a. MOLDABLE och iScheduling-policy, måste dock genomförandetiden justeras om en mängd resurser som är mindre än idealet beviljas. Dessutom måste kostnaden för skörd också inkluderas eftersom ansökan dras in medan omfördelning av resurser görs. För de experimentella applikationerna har man utvecklat ett exakt mått på överliggande anpassning [34] och har integrerats i simuleringen av användarcentrerade iSchedulers. Anpassningen av de allmänna omkostnaderna är i hög grad beroende av tillämpningen. Det beror på mängden data som överförs för att uppnå belastningsbalans som i sin tur beror på problemstorleken och antalet processorer. Den omfattar kostnaderna för omfördelning av data på klusternätverket och skapande av processer (för att lägga till processorer i applikationen). Men för superdatorns arbetsbörda spår, jobben är i huvudsak svarta lådor så att denna overhead inte kan vara känd. Den genomsnittliga löplängden för dessa applikationer är dock i 1000-talet av sekunder och vi har fastställt att anpassning overhead är typiskt i storleksordningen några sekunder i värsta [34]. Dessutom visar våra resultat att antalet adaptiva händelser är ganska litet (1-3 per applikation). De små jobben är vanligtvis enstaka CPU-jobb (ideal = min = 1) vilket innebär att de inte genomgår anpassningar, men kan dra nytta av dem. Därför ignoreras omkostnaderna för den systemcentrerade iScheduler-simuleringen, men ingår i den användarcentrerade iScheduler-simuleringen. Dessutom är den minsta mängden CPU-resurser inte heller tillgänglig från spåren. I stället ställer vi in detta som en parameter, min_%_of_ideal, som anger det minsta antalet nödvändiga resurser som en procentandel av dess ideal. Till exempel, om min_%_of_ideal är 10%, och ideal var 100, då min skulle vara 10. Vi varierar denna parameter för att generera arbetsbelastning spår. Att justera programlängden som en funktion av antalet resurser är också en fråga för superdatorjobben eftersom de är svarta lådor. För att ta itu med denna fråga har vi implementerat två gemensamma utförandemodeller inom simuleringen, (i) linjär och (ii) parabolisk. Den linjära modellen tar inte hänsyn till kommunikation och förutsätter att exekveringstiden är linjär i P. Den paraboliska modellen förutsätter att det finns kommunikation och att det perfekta antalet processorer (P ideal ) är den sanna minsta exekveringstiden. Detta leder till den klassiska paraboliska formen av utförande tid vs. processorer (Figur 2 ). De verkliga parallella applikationerna är 17 paraboliska, så denna modell används för den användarcentrerade iScheduler. Verkställighetstiden för båda modellerna är följande (P är antalet processorer): Om P ändras under körningen av applikationen (om iScheduling är aktiverat), tillämpas dessa funktioner för varje värde av P under lämplig varaktighet. Vi undersöker tre grundläggande frågor i denna studie. För det första: Ger iScheduling-paradigmet en resultatvinst jämfört med baslinjepolitiken? För det andra, vad är den mest effektiva iScheduling politik med tanke på det stora utrymmet av alternativ. För det tredje, vad är känsligheten hos iScheduler prestanda för arbetsbelastning och systemegenskaper. Vi bestämde prestandakänsligheten för M, graden av multiprogramming, och till min_%_of_ideal, den minsta tillåtna % av idealiska resurser. I allmänhet kommer M att variera från 3,6,9,12, och no_limit, och min_%_of_ideal från 50%, 40%, 30,%, 20% och 10% av ideal. Vi genererade 100 spår som innehöll 10000 jobb för varje simuleringsexperiment. De värden som presenteras är genomsnittet av de 100x10000 jobben. I den första jämförelsen jämförs basvärdena, IDEAL-ONLY, IDEAL-BACKFILL och MOLDABLE mot den enklaste skördebaserade politiken, Even-H-FQ för att se om skördebaserad politik är konkurrenskraftig med standardpolitiken (figur 9 ). Den simulerade maskinen innehåller 128 processorer. Vi visar resultat för både linjära och paraboliska utförandemodeller. För att möjliggöra en rättvis jämförelse med baslinjerna är M satt till att vara no_limit för Even-H-FQ, eftersom detta är standardinställningarna för baslinjerna. Det är uppenbart omedelbart att IDEAL-ONLY presterar ganska dåligt med avseende på väntetiden eftersom det kräver att vänta på det perfekta antalet resurser på ett FCFS-sätt. Eftersom väntetiden för IDEAL-ONLY dominerar den totala tiden (vänta tid + genomförandetid), utelämnar vi den från de återstående graferna i figur 9 eftersom det är betydligt värre än de andra politikerna (vi kommer att återgå till denna politik i slutet av detta avsnitt). Resultaten visar att Even-H-FQ uppnådde betydligt lägre väntetid än alla baslinjer, men att genomförandetiden går upp eftersom ansökningar kan köras med färre resurser under iScheduling. Den totala avslutningstiden är dock bättre för iScheduling för vissa värden av min_%_of_ideal (större värden), men inte för alla värden. Detta fastställer att iScheduling (åtminstone, Even-H-FQ) presterar gynnsamt för vissa värden av M och Vi jämför nu flera skördebaserade policys head-to-head. De jämförande resultaten av schemaläggningspolitiken skilde sig inte nämnvärt åt mellan de linjära och paraboliska tillämpningsmodellerna. Därför presenterar vi i de återstående graferna för den systemcentrerade iScheduler endast resultat för den linjära modellen. Vi visar väntetid och total tid (väntar tid + utförande tid) som de viktigaste måtten av intresse. I den första uppsättningen resultat jämför vi väntetiden under de fyra schemaläggning politik och deras känslighet för graden av multiprogrammering M (Figur 10 ). Resultaten visar att när min_%_of_ideal är 50%, *-FQ outperforms *-FR för M=3 och M=6. När det är 40%, FQ överträffar FR för M=3, 6 och 9. När det är 30%, *-FQ överträffar FR för M=3, 6, 9 och 12. Trenden är tydlig: som min_%_of_ideal minskar, *-FQ outperforms *-FR för ett bredare spektrum av M. Anledningen är att när min_%_of_ideal minskar, fler jobb är sannolikt berättigade att komma in i systemet, därför *-FQ kan utnyttja denna möjlighet lättare. I allmänhet, när M ökar för alla politikområden, minskar väntetiderna eftersom systemet är mer benägna att släppa jobb på maskinen. När M ökar till den punkt av no_limit, då väntetiderna alla konvergera till samma lilla värde. Anledningen är att när ett jobb avslutas försöker schemaläggningspolitiken först att tillfredsställa begränsningen på M, oavsett om det är *-FR eller *-FQ. När M-begränsningen har uppfyllts, då antingen kör eller ytterligare köade jobb beaktas. Så ett värde på no_limit är i huvudsak samma som *-FQ. Prestandan hos Low-Imp-* är något bättre än Even-H-* vilket inte är förvånande med tanke på att den beaktar effekterna på den skördade applikationen. Resultaten är dock tillräckligt likartade för att antyda att enkla strategier som Even-H-* är effektiva. Det är dock tydligt att FQ-alternativet minskar väntetiden. Nästa metriska att observera är den totala slutförande tid beroende på M (Figur 11 ). Politiken för *-FR uppnår bättre övergripande resultat jämfört med *-FQ när M ökar. När M ökar, *- Men om förkortad total tid önskas, då antingen schemaläggning policy med FR alternativet kommer i allmänhet att prestera bättre än FQ vid höga nivåer av multiprogrammering M. Resultaten tyder på att vi bör köra på hög M eftersom detta ger minskad total tid. FR är överlägsen FQ på hög M eftersom ett högt värde av M släpper in fler jobb i systemet vilket i sin tur innebär att många jobb kommer att köras under deras ideala antal processorer. Därför är en distributionsstrategi som kommer att gynna dessa löpande jobb bättre än att ge ytterligare större prioritet till köade jobb (en stor M redan gynnar köade jobb i viss utsträckning). Nästa fråga som vi undersökte var den jämförande prestandan hos schemaläggningspolitiken som en funktion av min_%_of_ideal. För det första visar vi väntetiden som min_%_of_ideal är varierad för fasta värden av M (Figur 12 ). Resultaten visar att i allmänhet som min_%_of_ideal minskar väntetiderna för *-FQ politik minskar. Denna trend är också observerad för *-FR under låga grader av multiprogrammering, men som graden av multiprogrammering ökar för *-FR politik, en minskning av min_%_of_ideal leder till högre väntetider. Anledningen är att eftersom min_%_of_ideal minskar finns det fler löpande jobb som är berättigade att få ytterligare resurser särskilt för större M. Därför, när M är nöjd, *-FR är mer benägna att fördela resurser till att köra jobb, vilket ökar väntetiderna för jobb i kön. Nästa mått att observera är det totala tidsberoendet av min_%_of_ideal (figur 13)
Weissman m.fl. REF beskriver en applikationsmedveten jobbplanerare som dynamiskt styr resursfördelningen mellan samtidiga jobb, med processer som skickar data till rotnoden för datadistribution.
Integrated Scheduling: The Best of Both Worlds
{'venue': 'Journal of Parallel and Distributed Computing', 'journal': None, 'mag_field_of_study': ['Computer Science']}