Att skapa högkvalitativa scheman för distribuerade applikationer på ett beräkningsgrid är ett utmanande problem. Vissa experiment med Simulated Annealing som schemaläggningsmekanism för en ScalaPACK LU-lösare på ett rutnät beskrivs. Den Simulerade Annealing schemaläggaren jämförs med en Ad-Hoc Greedy schemaläggare som används i tidigare experiment. Den Simulerade Annealing schemaläggaren avslöjar vissa antaganden inbyggda i Ad-Hoc schemaläggaren och några problem med Performance Model som används. Trots att det finns flera Grid-infrastrukturprojekt, såsom Globus [9] och Legion [11], är programplaneringen, genomförandet och övervakningen av applikationer på ett beräkningsunderlag fortfarande en användarintensiv process. Målet med projektet Grid Application Development Software (GRADS) [4] är att förenkla distribuerad heterogen databehandling på samma sätt som World Wide Web förenklade informationsdelningen. GRADS-projektet avser att tillhandahålla verktyg och teknik för utveckling och genomförande av tillämpningar i en Grid-miljö. Detta inbegriper uppgifter som att lokalisera tillgängliga resurser på rutnätet och schemalägga en ansökan på en lämplig delmängd av resurserna. Detta dokument kommer att presentera några experiment om automatiserad schemaläggning i en Grid-miljö. Schemaläggningen görs över en icke-homogen uppsättning Grid resurser bosatta på geografiskt olika platser, och använder dynamisk maskinstatus och konnektivitetsinformation från Globus Metacomputing Directory Service (MDS) [9, 10] och Network Weather System (NWS) [19]. Det naiva tillvägagångssättet att testa alla möjliga maskinscheman för att välja det bästa schemat blir snabbt intractable när antalet maskiner växer. När N-maskiner är tillgängliga, den naiva metoden skulle kräva att kontrollera cirka 2 N möjliga undergrupper av maskiner. Denna minsta exekveringstid multiprocessor schemaläggning problem är känd för att vara NP-hård i sin generaliserade form, och är NP-hård även i vissa begränsade former [16]. Många heuristik finns som kan användas för att minska sökutrymmet, och sökstrategier såsom giriga sökningar (som rankar maskinerna med hjälp av vissa kriterier), och (icke)-linjära programmeringssökningar (som försöker minimera en objektiv funktion med tanke på vissa begränsningar) kan användas för att hitta lösningar. Dessa tekniker innehåller dock i allmänhet inga mekanismer för att undvika lokala minima. Det finns många forskningsinsatser som syftar till att schemalägga strategier för rutnätet [5, 17, 18, 1, 2], se Berman [3] för en översikt över schemaläggning av rutnätet och en sammanfattning av alternativa tillvägagångssätt. Berman hävdar att en framgångsrik planeringsstrategi för Grid måste ta fram tidsramsspecifika prestandaprognoser, använda dynamisk information och anpassa sig till olika potentiella beräkningsmiljöer. Schemaläggning i GRADS-projektet tar dynamisk resursinformation om en distribuerad, heterogen rutnätsmiljö, och försöker skapa ett schema för att minimera körningstiden.
Den Simulerade Annealing schemaläggaren avslöjar vissa antaganden inbyggda i Ad-Hoc schemaläggaren och några problem med prestandamodellen som används REF.
Experiments with Scheduling Using Simulated Annealing in a Grid Environment ∗
{'venue': 'International Conference on Evolutionary Computation', 'journal': None, 'mag_field_of_study': ['Computer Science']}