Lygčių ir nelygybių simbolinio sprendimo lygiagretusis metodas

1 Įvadas 1.1 Dokumento paskirtis Šio dokumento paskirtis yra pateikti lygčių ir nelygybių simbolinio sprendimo lygiagretaus metodo architektūrinius ir algoritminius sprendimus, atlikti programų sistemos architektūros analizę, atlikti lygiagretaus algoritmo tyrimą. Antrajame skyriuje atliekama šio darbo srities anallizė, aprašomi pagrindiniai lygčių ir nelygybių tipai. Nustatomi skirtumai tarp skaitinių ir simbolinių išraiškų. Išnagrinėjamas galimų panaudoti kompiuterinės algebros sistemų sąrašas. Aptariami egzistuojantys lygiagrečių simbolinių skaičiavimų sprendimai. Trečiajame skyriuje aptariami sistemai keliami reikalavimai. Nustatomi panaudos atvejai, aprašomi funkciniai reikalavimai, numatomi apribojimai. Pagal šio skyriaus reikalavimus buvo realizuota programinė įranga. Ketvirtajame skyriuje aprašoma bendra sistemų sistemos architektūra, nustatomi ryšiai tarp sistemų. Aptariamas sistemų bendravimo principas (procesų kūrimas, bendravimas per socket„us). Aprašoma atviro kodo sistema, skirta matematinių išraiškų atvaizdavimui. Penktajame skyriuje aptariama Vartotojo PĮ (web programa) architektūra. Analizuojami MVC patern„o ir „Svogūno“ architektūros, priklausomybių injekcijos (Dependency Injection) privalumai, sukurtai PĮ. Aprašomas vartotojo duomenų (lygčių ir nelygybių sistemos) validavimas ir rezultatų pateikimas (kaip tekstinės išraiškos tampa paveiksliukais). Šeštasis skyrius skirtas Skaičiavimų PĮ (C++ MPI programa) architektūros aptarimui. Apibrėţiamas socket„ais (kompiuterio prievadais, port„ais) grįstas bendravimas tarp procesų. Pateikiamas Maxima CAS (kompiuterinės algebros sistema) panaudojimas kitos programos kontekste. Apţvelgiama MPI lygiagrečių skaičiavimų biblioteka ir jos panaudojimas. Septintajame skyriuje pateikiamas lygiagretaus sprendimo metodas. Pateikiama bendra algoritmo schema, valdančiojo proceso algoritmo dalies schema, skaičiavimų procesų algoritmo schema. Pateikiami apribojimai lygčių ir nelygybių sistemoms ir pavyzdţiai. Aštuntajame skyriuje pateikiamas skaičiavimų algoritmo tyrimas. Ištiriamos bendros algoritmo charakteristikos, nustatant priklausomybes tarp procesų kiekio, dalinių uţdavinių kiekio, matuojant algoritmo vykdymo laiką. Atliekamas sprendimų greičio palyginimas su Maple kompiuterinės algebros sistema. 9 1.2 Santrauka Pateiktas lygčių ir nelygybių simbolinio sprendimo lygiagretus algoritmas ir jo analizė, palyginimas su neefektyvia algoritmo realizacija. Atliktas įgyvendinto algoritmo tyrimas, nustatant jo spartos priklausomybes nuo aplinkos ir uţduoties, palyginant rezultatus su esama PĮ. Taip pat, šiame darbe aptariami sukurtos programų sistemos architektūriniai sprendimai: MVC patern„as (design pattern), „Svogūno“ architektūra, priklausomybių injekcijos (Dependency Injections). Šie architektūriniai sprendimai yra pranašesni uţ standartinę sluoksninę architekūrą, jais paremta PĮ yra lengviau palaikoma ir modifikuojama. Šiais laikais dauguma kompiuterių turi daugiabranduolius procesorius, tačiau esama PĮ jų neišnaudoja. Šio darbo tikslas yra sukurti tokią lygčių ir nelygybių simbolinio sprendimo lygiagrečiu metodu realizaciją, kuri panaudodama turimą skaičiavimų galią, sutrumpintų skaičiavimų laiką. Atlikus tyrimus nustatyta, jog sukurtoji PĮ yra pranašesnė uţ Maple CAS tik tuo atveju, kai uţdavinio sąlyga nėra didelė, bet reikalaujama didelės skaičiavimų galios (nelygybių sistemų sprendimas). Tačiau sprendţiant didelės apimties lygčių sistemas (40-50 neţinomųjų ir tiek pat lygčių) sukurtoji PĮ atsilieka nuo Maple CAS, kadangi daug laiko sugaištama nagrinėjant pateiktą uţduotį ir skaidant ją į dalinius uţdavinius. 10 2 Srities analizė Šiame skyriuje apţvelgiama:  Pagrindiniai lygčių ir nelygybių tipai: Tiesinės, polinominės, diophantine, inversinės, faktorizacinės, kompleksinių šaknų, Taylor„o eilutės, matricinės, diferencialinės, integralinės  Lygčių ir nelygybių sprendimo algoritmų įgyvendinimo sunkumai kyla dėl didelio kiekio lygčių ir nelygybių tipų, tipai turi atskirus atvejus. Taip pat sudėtingumo prideda simboliniai skaičiavimai, algoritmo lygiagretinimas, nelygybių sprendimas.  Simbolinės lygtys ir nelygybės yra tokios, kur koeficientai ţymimi simboliai, operacijos atliekamos ne su skaičiais, pasiţymi išraiškų suprastinimu, o rezultatai nepraranda tikslumo.  Kompiuterinės algebros sistemos: pateikiamas CAS apibrėţimas, galimybės, sąrašas. Pateikiamas tinkamos CAS pasirinkimas.  Kompiuterinės algebros sistema – Maxima: istorija, galimybės, vartotojo sąsaja.  Egzistuojantys lygiagrečių skaičiavimų sprendimai: įprastos CAS palaiko vieną procesą, „Parallel Fourier-Motzkin elimination“ algoritmas, esamos paskirstyto skaičiavimo sistemos. 2.1 Pagrindiniai lygčių ir nelygybių tipai Lygtys pagal savo savybes daţniausiai skirtomos pagal tokius tipus [12]:  Tiesinės lygtys ir jų sistemos – paprasčiausios visiems paţįstamos pirmojo laipsnio lygtys Pav. 1: Tiesinės lygties pavyzdys 11  Polinominės lygtys – lygtys, kurių neţinomieji turi laipsnius, didţiausias laipsnis nulemia šaknų skaičių Pav. 2: Polinominės lygties pavyzdys  Diophantine tipo lygtys – polinominių lygčių tipas, naudojami tik sveiki skaičiai. Neţinomųjų būna daugiau negu lygčių, tenka surasti visus tinkamus sprendinių variantus. Pav. 3: Diophantine lygties pavyzdys  Inversinės lygtys – šiam lygčių tipui priklauso lygtys su neigiamais laipsniais, logaritmais, inversinės trigonometrinės funkcijos.  Factorizacija paremtos lygtys – lygtys, kurios sprendţiamos iškeliant bendrą dauginamajį prieš skliaustus ir sprendţiant naujas lygtis atskirai. Pav. 4: Faktorizuojamos lygties pavyzdys (3 sprendimo žingsniai)  Kitos lygtys – lygtys su kompleksinėmis šaknimis, Taylor„o eilutės, matricinės lygtys, diferencialinės lygtys, integralinės lygtys ir t.t. Nelygybes kaip ir lygtis galima suskirstyti pagal panašius tipus, tačiau nelygybės pasiţymi išskirtinėmis savybėmis:  Pagrindinis pastebimas skirtumas yra išraiškos ţenklas, kai lygybė turi sprendinį grieţtai apibrėţiantį ţenklą „=“, nelygybės turi keturis – „“, „≤”, “≥”.  Remiantis ankstesniąja sąlyga, lygtys turi šaknis, o nelygybių sprendinys yra reikšmių intervalas, su ribinių reikšmių įtraukimu, priklausomai nuo ţenklo. 2.2 Lygčių ir nelygybių spredimo algoritmų įgyvendinimo sunkumai Didţiausia problema yra ta, kad nėra vienintelio algoritmo, kuris išspręstų visas lygtis ir nelygybes. Iš pradţių vykdoma uţdavinio analizė, gaunami jo parametrai, pagal juos nusprendţiama kaip sistema bus sprendţiama. 12 Kiekvienas lygčių ir nelygybių tipas turi skirtingus sprendimo algoritmus. Dėl šios prieţasties neįmanoma apimti didelio tipų kiekio. Tiesinių lygčių sprendimui naudojami paprastesni algoritmai, tokie kaip Gauso metodas [19]. Netiesinės lygtys turi sudėtingesnius algoritmus, po kuriais slepiasi teoremos, statistika, spėjimai. Tačiau, daţniausiai neuţtenka vieno algoritmo vienam lygybių tipui. Netgi atskiri šių tipų atvejai, priklausantys nuo sistemos parametrų turi skirtingas algoritmų realizacijas. Kaip pavyzdį galima paimti polinomines lygtis ir atskirą jų šaką Diophantine lygtį. Pastaroji operuoja tik su sveikais skaičiais, šaknimis gali būti tik sveikieji skaičiai, o neţinomųjų kiekis būna didesnis uţ lygčių kiekį. Sprendţiamos gali būti skaitinės ir simbolinės sistemos [18]. Skaitinės sistemos yra paprastesnės, jose koeficientai yra skaitinės reikšmės. Šias sistemas išspręsti uţtenka paprastų matematinių operacijų. Sudėtingesnės yra simbolinės sistemos, jose koeficientai yra ţymimi konstantomis (pvz. a, b). Kadangi neįmanoma atlikti matematinių veiksmų su tokiomis išraiškomis, tenka atlikti leksikinę analizę – veiksmus atlikti ne su skaičiais, o su išraiškomis. Vienas didţiausių iššūkių yra lygiagrečių algoritmų realizavimas. Šie algoritmai turi veikti greičiau uţ savo vieno proceso algoritmo atitikmenį ir grąţinti tuos pačius rezultatus. Kadangi yra galybė sistemų tipų ir atvejų, kiekvieno algoritmo realizacija yra didţiulis uţdavinys. Nelygybių sprendimas yra daug sudėtingesnis uţ lygybių sprendimą. Tai yra todėl, kadangi rezultate gaunamos ne šaknys, o išraiškos. Grafiškai išsprendus dviejų tiesinių lygčių sistemą gaunamas vienas taškas (jeigų lygtimis aprašomos tiesės susikerta), nelygybių atveju gaunamas plotas apribotas tiesėmis. Vienas geriausių ţinomų algoritmų, nelygygėms spręsti, yra „Fourier-Motzkin elimination“ [6] algoritmas. Šis algoritmas remiasi kintamųjų atmetimu iš sistemos. Tačiau šio algoritmo sudėtingumas yra dvigubai eksponentinis, t.y. skaičiavimo laikas ypač greitai kyla didėjant nelygybių ir neţinomųjų kiekiui. 13 Pav. 5: Dviejų tiesių susikirtimas, lygybių atveju rezultatas taškas, nelygybių atveju, vienas iš keturių plotų Taigi norint įgyvendinti lygiagretų lygčių ir nelygybių sprendimą tektų realizuoti daugybę simbolinių lygčių sistemų sprendimą lygiagrečiai ir „Fourier-Motzkin elimination“ lygiagretaus algoritmo versiją simboliniams skaičiavimams. Šio uţdavinio sudėtingumo sumaţinimui buvo pasirinkta kompiuterinės algebros sistema „Maxima“ [16], kuri turi realizuotus nelygiagretaus skaičiavimo algoritmus simboliniams skaičiavimams, tad šie skaičiavimai bus lygiagretinami pasinaudojus MPI [15] lygiagretaus skaičiavimo bibliotekomis. 2.3 Simbolinės lygtys ir nelygybės Vienas labiausiai pastebimas skirtumas tarp simbolinės ir skaitinės išraiškos yra tas, kad vietoj koeficientų yra naudojami simboliai (daţniausiai raidės: „a“, „b“ ir t.t.). Tačiau nevisi koeficientai turi būti simboliai, norint atlikti simbolinius skaičiavimus, gali ir nebūti nei vieno simbolio, kuris aprašytų koeficientą. Veiksmai su simbolinėmis išraiškomis yra daug sudėtingesni negu su skaitinėmis išraiškomis. Simbolinės išraiškos atveju nevisada galima atlikti matematines operacijas su koeficientais, kadangi jais gali būti ne tik skaičiai bet ir simboliai, įvedamas specialus simbolio tipas, perrašomos pagrindinės operacijos šiam simbolio tipui. Svarbi simbolinės išraiškos savybė yra išraiškos suprastinimas arba pakeitimas, pakeičiant vieną išraišką kita arba kitomis, nepakeičiant jos reikšmės. Svarbiausia simbolinės išraiškos savybė yra tikslumas. Atlikus simbolinius skaičiavimus gaunama tiksli reikšmė, kadangi nėra paklaidos, kuri įsivelia atliekant skaitinius skaičiavimus. Kodėl skaitiniai skaičiavimai turi paklaidą, o simboliniai neturi? Skaitiniai algoritmai atlieka operacijas su real tipo skaičiais, daţnai šaknų ieško iteraciniais metodais artėdami link jų reikšmių. Tuo tarpu simboliniai skaičiavimai nedirba su real tipo skaičiais, jie remiasi išraiškų 14 suprastinimais ir veiksmais su simbolinėmis išraiškomis. Geras pavyzdys yra lygties sprendinys šaknis iš 3, skaitinis metodas grąţintų reikšmę 1,732050807. O simbolinis metodas graţintų rezultatą kaip sqrt(3). Jeigu šis rezultatas būtų naudojamas tolesniam kitų sistemų sprendimui, skaitinio metodo atveju tikslumas būtų toliau prarandamas, o simbolinio metodo atveju tikslumas nenukentėtų. Pav. 6: Simbolinė lygčių sistema ir jos sprendinys 2.4 Kompiuterinės algebros sistemos Kompiuterinės algebros sistema [3] (CAS – computer algebra system) yra programinė įranga atliekanti simbolinius matematinius skaičiavimus. Simbolinius skaičiavimus daţniausiai sudaro:  Išraiškos prastinimas į maţesnę ar standartinę formą  Simbolių ar išraiškų keitimas į kitas išraiškas  Laipsnių išskleidimas, faktorizavimas, trupmenų pertvarkymas  Diferenciacija (diferenciacijos operacija)  Integravimas  Simbolinių išraiškų optimizavimas  Tiesinių ir kai kurių netiesinių lygčių sprendimas  Kai kurių diferencialinių lygčių sprendimas  Ribų paieška Išraiškas daţniausiai sudaro polinomai, standartinės funkcijos (sinusas, eksponentė), įvairos specialios funkcijos (pvz. Bassel funkcija), integralai ir t.t. Šiame darbe domina tik tos kompiuterinės algebros sistemos, kurios palaiko lygčių ir nelygybių sprendimą. Sąrašas [2] tokių sistemų: 15 Lentelė 1: Kompiuterinių algebrinių sistemų, sprendžiančių lygčių ir nelygybių sistemas, lentelė P av ad in im as K ū rė ja s A r k o m er ci n ė? P ra d ėt a v y st y ti ( d at a) P ir m o ji v ie ša re al iz ac ij a (d at a) Iš la ik o re zu lt at ų ti k sl u m ą S p re n d ţi a ly g či ų si st em as S p re n d ţi a n el y g y b ių si st em as Algebrator Neven Jurkovic Taip 1986 1999 Ne Taip Taip Maple Symbolic Computation Group, University of Waterloo Taip 1980 1984 Taip Taip Taip Mathematica Wolfram Research Taip 1986 1988 Taip Taip Taip Maxima MIT Project MAC and Bill Schelter Ne 1967 1998 Taip Taip Taip Microsoft Mathematics Microsoft Ne - 2005 Ne Taip Taip Sage William A. Stein Ne 2005 2005 Taip Taip Taip Xcas Bernard Parisse Ne 2004 2008 Taip Taip Taip Simboliniams skaičiavimams atlikti reikia pasirinkti labiausiai tinkamą kompiuterinės algebros sistemą. Ši sistema neturi būti komercinė, atlikti simbolinius skaičiavimus – išlaikant rezultatų tikslumą. Tarp galimų CAS yra Maxima, Sage ir Xcas. Sage yra Python kalba realizuota CAS, tačiau tai nėra tikra algebrinė sistema, ji naudoja kitus paketus skaičiavimams atlikti, o jos priėjimas yra tik per naršyklę (panaši koncepcija į šio magistrinio darbo programą). Dėl šios prieţasties ši sistema nėra panaudojama. Xcas yra C++ kalba realizuota, vartototojo sąsaja paremta (langai), CAS. Ši sistema nėra plačiai paplitusi, o jos panaudojimas (kaip ir Sage ateveju) kitame kontekste yra beveik neįmanomas, tenka atsisakyti ir šio pasirinkimo. Maxima yra Common Lisp [7] kalba realizuota CAS, turinti tiek konsolinę, tiek ir langų vartotojo sąsają. Įdomi šios sistemos savybė yra galimybė su konsole bendrauti per socket„us, t.y. siuntinėti ir gauti pranešimus iš kito proceso. Dėl šios prieţasties ir buvo pasirinkta ši sistema. 2.5 Kompiuterinės algebros sistema – Maxima Maxima yra kompiuterinės algebros sistema, kurios pagrindą sudarto 1982 metų Macsyma [13] (Project MAC‟s SYmbolic MAnipulator) versija. Maxima yra parašyta Common Lisp kalba ir veikia visose POSIX platformose tokios kaip Mac OS X, Unix, BSD, ir GNU/Linux, taipogi Microsoft Windows. Tai yra nemoka programinė įranga turinti „GNU General Public License“ licenziją. 16 Maxima turi uţbaigtą programavimo kalbą, kurios sintaksė panaši į ALGOL, o ţymėjimai į Lisp kalbos. Kadangi sistema yra parašyta Common Lisp kalba, sistemos funkcionalumą gali išplėsti pats vartotojas sukurdamas naujas funkcijas ir jas kviesdamas iš Maxima aplinkos. Maxima yra pilnai realizuota CAS, kurios paskirtis yra atlikti simbolinius skaičiavimus, tačiau ji gali atlikti ir skaitinius skaičiavimus su sveikais ir realiais skaičiais, kurių reikšmes apriboja tik turima kompiuterio atmintis. Dėl šios prieţasties realieji skaičiai gali praktiškai turėti begalinį tikslumą (skaitmenų kiekis po kablelio). Skaičiavimams, kurie ypač naudoja daug realių reikšmių, Maxima gali sugeneruoti kitų kalbų (pvz. Fortran) kodą, kuris bus vykdomas daug greičiau negu Common Lisp. Maxima turi daugybę grafinių sąsajų, tokių kaip „wxMaxima“, „Cantor“, „GNU TeXmacs“, „Lyx“. Tačiau šiame magistriniame darbe labiausiai domina konsolinė versija. Pav. 7: Maxima grafinė sąsajos, kairėje sąsajos langas Windows sistemoje, dešinėje konsolė Linux sistemoje 2.6 Egzistuojantys lygiagrečių skaičiavimų sprendimai Visos kompiuterinės algebros sistemos sugebančios simboliškai spręsti lygčių ir nelygybių sistemas, tai daro pasitelkdamos tik vieną procesą, t.y. nevykdo lygiagrečių skaičiavimų. Tai yra todėl, kad tam tikrais atvejais yra per brangu sukurti teisingą algoritmą, pigiau yra didinti skaičiavimo mašinos galią. Tačiau yra ir išimčių, tokių kaip matricų sudėtis, daugyba ir panašūs veiksmai, nereikalaujantys ypač specializuotų algoritmų, rezultatų radimui. Tarp mokslinių straipsnių galima rasti ne tik „Fourier-Motzkin elimination“ (algoritmas nelygybėms spręsti) bet ir „Parallel Fourier-Motzkin elimination“ [1] algoritmo teorinius įgyvendinimus. Tačiau tokio lygiagretaus algoritmo įgyvendinimas uţtruktų nemaţai laiko, 17 kadangi kiekvieno nelygybių tipo atvejis turi būti nagrinėjamas atskirai, simbolinis skaičiavimas ir netiesinės nelygybės prideda dar daugiau sudėtingumo. Egzistuoja keli paskirstytų skaičiavimų atlikimo tinkle paketai: „HPC-Grid for Maple“ [8] ir „Parallel Computing Toolkit“. Pirmasis naudoja „Maple“ CAS, o antrasis „Mathematica“ CAS. Tačiau šie paketai atlieka tik darbų paskirstymą kompiuterių tinkle, surenka rezultatus, dauguma funkcijų yra naudojama iš standartinių kompiuterinės algebros sistemų, tik kai kurios yra pakeičiamos aukštu lygiu išlygiagretintomis komandomis. 18 3 Reikalavimai sistemai Šiame skyriuje apţvelgiama:  Panaudos atvejai: pateikti lygčių ir nelygybių sistemą, gauti lygčių ir nelygybių sistemos sprendinį.  Funkciniai reikalavimai: duomenų validacija, skaičiavimų būsenos sekimas, rezultatų pateikimas, skaičiavimų istorijos naršymas.  Apribojimai sprendimui: panaudoti C++ MPI biblioteką, pritaikyti naršyklei, naudojimas be specialios PĮ ar ţinių. 3.1 Panaudos atvejai Kadangi sistema sprendţia algoritminį uţdavinį, tėra tik du būtini panaudos atvejai. Pirmasis yra pateikti lygčių ir nelygybių sistemą, o antrasis yra sulaukti atsakymo. Atsakymo gavimas yra traktuojamas kaip panaudos atvejis, kadangi sprendimas uţima šiek tiek laiko, vartotojas gali išeiti iš uţdavinio lango, tada norėdamas pamatyti sprendinį, jis turi naviguoti atgal į tos uţduoties langą. Taip pat yra papildomų panaudos atvejų kurie yra realizuoti, bet nėra būtini. Tokie kaip: neţinomųjų generavimas iš sistemos, spręstų uţdavinių sąrašo perţiūra, veiksmų atšaukimas ir panašiai. Pav. 8: Panaudos atvejai 19 Panaudojimo atvejis 1: Pateikti lygčių ir nelygybių sistemą Aktorius: vartotojas Tikslas: skirta pateikti lygčių ir nelygybių sistemą programinei įrangai, jai suprantamu formatu Ryšiai su kitais PA: sukelia “Gauti lygčių ir nelygybių sistemos sprendimą” panaudos atvejį Prieš-sąlygos: vartotojas pasiruošia duomenis, kuriuos pateiks sistemai Sužadinimo sąlyga: vartotojas pasirinko duomenų parteikimą vartotojo sąsajoje Po-sąlyga: sistema apdoroja pateiktus duomenis Pagrindinis scenarijus: 1. Vartotojas parengia duomenis skirtus apdoroti sistemai 2. Vartotojas pateikia duomenis sistemai 3. Sistema vykdo skaičiavimus Alternatyvūs scenarijai: Vartotojas pateikia netinkamus duomenis, pranešamos klaidos, skaičiavimai nevykdomi Panaudojimo atvejis 2: Gauti lygčių ir nelygybių sistemos sprendinį Aktorius: vartotojas Tikslas: skirta pateikti lygčių ir nelygybių sistemos rezultatus vartotojui tinkama forma Ryšiai su kitais PA: šis panaudos atvejis gali įvykti tik tada, kai prieš tai yra suţadinamas “Pateikti lygčių ir nelygybių sistemą” panaudos atvejis Prieš-sąlygos: vartotojas prieš tai pateikė teisingus duomenis Sužadinimo sąlyga: vartotojas pasirinko rezultatų perţiūra vartotojo sąsajoje Po-sąlyga: vartotojas pasiima rezultatus Pagrindinis scenarijus: 1. Sistema apskaičiuoja sprendinį 2. Vartotojas sistemai pateikia uţklausą dėl rezultatų gavimo 3. Rezultatai pateikiami vartotojui Alternatyvūs scenarijai: Sistema dar nespėjo įvykdyti skaičiavimų 20 3.2 Funkciniai reikalavimai Sistemai buvo iškelti keturi funkciniai reikalavimai: 1. Vartotojo duomenų validacija, nes tik tinkamai pateiktas sistemas galima išspręsti 2. Skaičiavimas turi turėti būseną. Esamos būsenos: „Sprendţiama“ ir „Išspręsta“. 3. Rezultatai pateikiami vartotojui skaitomu formatu, uţdavinio detalėse rezultatus pavaizduojamas suformuotu paveikslėliu, sąraše paprastu tekstu 4. Vartotojas turi galimybę atsidaryti bet kokio anksčiau vykdyto skaičiavimo detales Reikalavimas #: 1 Reikalavimo tipas: 9a Įvykis/panaudojimo atvejis #: 1 Aprašymas: Sistema privalo pranešti vartotojui apie neteisingus pateiktus pradinius duomenis Pagrindimas: Uţtikrinamas tinkamas programinės įrangos veikimas Šaltinis: Vartotojas Tikimo kriterijus: Sistema dirba tik su tinkamais duomenimis Uţsakovo tenkinimas: 4 Uţsakovo netenkinimas: 4 Priklausomybės Nėra Konfliktai: Nėra Papildoma medţiaga: Istorija: Uţregistruotas 2010 kovo 28 d. Reikalavimas #: 2 Reikalavimo tipas: 9a Įvykis/panaudojimo atvejis #: 1 Aprašymas: Sistema vartotojui praneša apie tikėtiną skaičiavimų ilgumą ir/ar būseną Pagrindimas: Vartotojas turi informaciją apie skaičiavimų atlikimą Šaltinis: Sistema Tikimo kriterijus: Vartotojas ţino kada tikėtis rezultatų Uţsakovo tenkinimas: 5 Uţsakovo netenkinimas: 3 Priklausomybės Nėra Konfliktai: Nėra Papildoma medţiaga: Istorija: Uţregistruotas 2010 kovo 28 d. 21 Reikalavimas #: 3 Reikalavimo tipas: 9a Įvykis/panaudojimo atvejis #: 2 Aprašymas: Sistema pateikia sprendinius vartotojui priimtinu formatu Pagrindimas: Vartotojas sugeba teisingai interpretuoti rezultatus Šaltinis: Sistema Tikimo kriterijus: Vartotojas gauna rezultatus Uţsakovo tenkinimas: 4 Uţsakovo netenkinimas: 4 Priklausomybės Nėra Konfliktai: Nėra Papildoma medţiaga: Istorija: Uţregistruotas 2010 kovo 28 d. Reikalavimas #: 4 Reikalavimo tipas: 9a Įvykis/panaudojimo atvejis #: 2 Aprašymas: Vartotojas gali gauti anksčiau įvykdytų skaičiavimų rezultatus Pagrindimas: Vartotojui gali prireikti gauti anksčiau vykdytų sprendimų rezultatus Šaltinis: Vartotojas Tikimo kriterijus: Vartotojas passima ankstesnių skaičiavimų rezultatus Uţsakovo tenkinimas: 3 Uţsakovo netenkinimas: 3 Priklausomybės Nėra Konfliktai: Nėra Papildoma medţiaga: Istorija: Uţregistruotas 2010 kovo 28 d. 3.3 Apribojimai sprendimui  Sistemos kūrime panaudoti C++ MPI biblioteką  Vartotojas sistemą turi pasiekti per naršyklę  Vartotojas neturi įsidiegti specializuotos PĮ 22 4 Bendra architektūra Šiame skyriuje apţvelgiama:  Programų sistemą sudaro Vartotojo PĮ, Skaičiavimų PĮ ir Eq2Img atviro kodo sistema.  Bendravimas tarp Vartototojo PĮ ir Skaičiavimų PĮ procesų naudojant socket„us. Bendravimo ţingsniai iš Vartotojo PĮ pusės ir iš Skaičiavimų PĮ pusės.  Uţdavinio sistemų ir rezultatų atvaizdavimas vartotojui atliekamas naudojant Eq2Img atviro kodo sistemą, verčiant tekstą į paveikslėlį. 4.1 Bendras sistemos vaizdas Šią programų sistemą sudaro trys dalys:  Vartotojo PĮ  Skaičiavimų PĮ  Eq2Img [4] (tekstu uţrasytų lygčių ir nelygybių vertimas į paveikslėlius) Vartotojo PĮ ir Eq2Img yra Web programos, todėl jos yra „hostinamos“ IIS (Internet Information Service) aplinkoje. Ši aplinka leidţia šias programas pasiekti per naršyklę. Abi IIS programos yra parašytos ASP.NET aplinkoje, C# kalba. Vartototojo PĮ yra sukurta šio magistrinio darbo metu, o Eq2Img yra atviro kodo sistema, kuri LaTex [11] išraiškas verčia į ţmonėms lengviau suvokiamus paveiksėlius. Skaičiavimų PĮ yra realizuota C++ kalba, panaudojant lygiagretaus programavimo biblioteką MPI. Šią programą valdo Vartotojo PĮ. Pav. 9: Programų sistemos veikimo principas IIS Vartotojo PĮ Skaičiavimų PĮ (1) sukuriami procesai, perduodama uţduotis (2) per socket kanalą grąţinami rezultatai (3) rezultatai perduodami per URL (4) sugene- ruojamas ir grąţinamas paveiksliukas Eq2Img PROGRAMŲ SISTEMA 23 Vartotojo PĮ suteikia vartotojui prieigą prie sistemos per naršyklę. Vartotojas sukuria naują uţdavinį, įrašo sąlygą. Jeigu sąlyga neteisinga, parodomi klaidų pranešimai, kol vartotojas įrašo tinkamą sąlygą. Tada programa pertvarko pateiktą uţduotį, išsaugo ją duomenų bazėje ir kuria Skaičiavimų PĮ procesus MPI aplinkoje, per argumentus perduodant uţduotį. Vartotojo PĮ turi procesą, kuris socket„ų pagalba gauna rezultatą iš Skaičiavimų PĮ. Rezultatas pertvarkomas su Eq2Img ir atvaizduojamas kaip paveikslėlis. Pav. 10: Vartotojo PĮ veikimo principas Vartotojo PĮ sukuria Skaičiavimo PĮ procesus MPI aplinkoje. Turi būti sukurti bent du procesai, nes vienas bus valdantysis, o kiti skaičiavimų. Kadangi ši programa yra parašyta C++ kalba, uţduotis jai perduodami per programos įėjimo taško (EntryPoint) argumentus. Taip pat paduodamas Vartotojo PĮ socket adresas, kuriuo grąţinti rezultatą. Gauta uţduotis išsprendţiama ir valdantysis procesas išsiunčia rezultatą į Vartototojo PĮ. Pav. 11: Skaičiavimų PĮ veikimo principas VARTOTOJO PĮ Uţduotis Rezultatas Atvaizdavimas Skaičiavimų PĮ Eq2Img (1) sukuriami procesai, perduodama uţduotis (2) per socket kanalą grąţinami rezultatai (3) rezultatai perduodami per URL (4) sugene- ruojamas ir grąţinamas paveiksliukas SKAIČIAVIMŲ PĮ (1) sukuriami procesai, perduodama uţduotis (2) per socket kanalą grąţinami rezultatai Uţduotis Rezultatas Uţduoties sprendimas Vartotojo PĮ Uţduoties validacija ir pertvarkymas 24 4.2 Bendravimas tarp Vartototojo PĮ ir Skaičiavimų PĮ procesų Socket„ai [20] yra vienas efektyviausių būdų bendrauti tarp dviejų procesų. Socket„ai naudoja prievadus (ports) kaip adresus, kuriais yra keičiamasi duomenimis. Įdomi socket„ų savybė yra ta, kad jie nepriklauso nuo programavimo kalbos ir remiasi serverio – kliento architektūra. Šioje programų sistemoje socket„ų pagalba bendrauja Vartotojo PĮ (C# kalba) ir Skaičiavimo PĮ (C++ kalba). Šiuo konkrečiu atveju bendravimas vyksta tik į vieną pusę – Skaičiavimo PĮ (klientas) siunčia rezultatus tam tikru ţinomu adresu Vartotojo PĮ (serveris). Ţemiau esantis paveikslėlis parodo visą bendravimo procesą, pav. 12. Vartototojo sąsaja turi PendingProblemService servisą, kuris sukasi visą programos veikimo laiką. Kuriant šį servisą yra sukuriamas socket„ų serveris ir pririšamas prie tam tikro prievado numerio (diapazone 2000-2099). Suradus laisvą prievadą serveris pradeda jo klausytis, kol kas nors juo pasiųs duomenis. Turime paveikslėlyje parodytą ţingsnį (1). Vartotojui įvedus uţduotį ji yra išsaugojama duombazėje, gaunamas uţduoties Id ir pati uţduotis, ţingsnis (2). Tada sukuriami Skaičiavimų PĮ procesai. Sukonstruojama tokia eilutė: /c mpiexec -n

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!