Т- жүйесі

Т-жүйесін құру өткен ғасырдың 80-ші жылдарының соңында РҒА (РАН)-ның бағдарламалық жүйелер Институтында басталған болатын.

Т-жүйесіне тән негізгі ерекшелік: бағдарламаларды динамикалық параллельдеуді қамтамасыз ету үшін функционалды бағдарламалау парадигмасын пайдалану болып табылады. Осының негізінде параллель есептеуді ұйымдастыру үшін Т-жүйесінде қызықты формаларды жүзеге асыруға және де табуға мүмкіндік туды. Мысалға алсақ, жүктемені бөлу немесе синхрондау үшін. Сонымен қатар, Т-жүйесінің функционалды стилін С, С++ тілдерінің кеңейтілуі немесе Fortran тілі көмегімен дәстүрлі бағдарламалау тілдерімен бірге тиімді пайдалану мүмкіндігі туды. Бұл тілде нақты параллельді конструкция жоқ және де бағдарламашы мәтінде бағдарламаның қай бөліктерін параллель орындау керек екенін анық көрсетпейді.

Т-жүйесінің базалық қағидалары функционалды бағдарламалаудың жалпы теориясының нәтижелеріне негізделген. Оны айқындау, түсіндіру үшін теорияның әрбір бөлігіне мән бермей-ақ сол сияқты жай теорияларды, яғни қарапайым аналогтарын пайдалануға болады. Мысалға, бір күрделі арифметикалық өрнек бар болып, оған өз кезегінде көптеген жақшаға алынған өрнекшелер кірсін делік. Әрине, бұл есептің шешімін кезкелген тәртіппен шешуге болады және әр жағдайда да нәтижесі бірдей болады. Функционалды бағдарлама теориясында арифметиканың бұл заңы еркін рекурсивті функцияларға да жалпыланады.

Бұндай тәсіл бізге «таза» функциялардан құрылған функционалды бағдарламаларды параллельдеу үшін тіке әдісті береді. Таза функциялар дегеніміз қосалқы әсерсіз функцияларды білдіретін Т-жүйенің базалық ұғымдарының бірі болып табылады. Әрбір уақыт мезетінде есептеуге дайын «өрнекшелерді» белгілеп алып, оларды пайдаланудағы процессорларға бөліп беру керек. Бұл жерде негізі ретінде, түйіндері -шақырылған функцияларды көрсететін, ал доғалары - «өрнекше-өрнек» қатынасына сәйкес келетін граф алынады.

Дәстүрлі бағдарламалау тіліне функционалды семантиканы қосу үшін, «дайын емес мән» ұғымын енгізу жеткілікті болады екен. Бұл С тілінде айнымалыларды сипаттауда қосымша атрибутты енгізу арқылы жүзеге асырылады. Жаңа tval кілттік сөзі « tvalint i » сипаттауында мәні бүтін немесе дайын емес мән болатын айнымалыны анықтайды. Қосалқы әсерсіз функцияларды белгілеу үшін қосымшаtfun сөзін қолданады. Шығу Т - функциясы tout сөзімен белгіленеді. және т.б.

Қарапайым мысал қарастырайық:

tfun void tmain(...) {

tval int x, у, z, b = 1;

int w, t, a = 5;

G(a, b, &x, &y, &z); /* x, у, z –те нәтижелерді қабылдау*/

b = z;

У = a;

w = a;

t = b+a*w;

…

}

Берілген G функциясы таза және онда tfun атрибуты бар деп есептейік. Мысалды «қадам» бойынша орындаймыз.

1. G (a, b, &x, &y, &z). G функциясы таза болғандықтан ол негізгі бағдарламамен параллель орындалуы мүмкін. Осы оператор орындалғаннан кейін Т-жүйесі G-функциясының шақырылуының негізінде, параллель орындалуға дайын жаңа жұмыс үлесін рәсімдейді.

Бұл жұмыс үлесі тез арада орындалуы да, немесе басқа себептер болып оның орындалуы кейінге қалдырылуы да мүмкін. Қай жағдайда да жүйе келесі операторды орындауға көшеді. Айнымалылар x, y, z - дайын емес айнымалылар статусын алады және дайын емес мәндерді қабылдайды.

2. b = z. Енді b айнымалысы да дайын емес болды, ал жүйе ешқандай бөгеліссіз одан ары бағдарламаны орындайды. Бұл мысал, дайын емес мәндерді көшіруге болатынын көрсетеді. Бірмезетте біз G функциясы нәтижесінің тұтынушылар құрамын да өзгерттік. Енді үшінші нәтиже Z айнымалысына да, дәл осылай B айнымалысына да берілуі тиіс. Әрине, осы мезеттегі b айнымалысының дайын емес екендігі, G функциясының аргументі ретінде алынған b мәніне еш әсер етпейтінін байқаймыз.

3. y = a. Айнымалы а - жай, сондықтан дайын емес y айнымалысы дайын болады және де а айнымалысының мәнін қабылдайды.

4. w = a. Бұл оператордың орындалуында қиыншылық туындамайды, себебі мұнда жай айнымалылар пайдаланылған.

5. t=b+a*w. Бұл операторда фрагменттің орындалуы, қашан G функциясы b айнымалысының нәтижесін қайтармайынша бұғаттауда болады. Екінші оператордағыдай, мұнда дайын емес мәндерді көшіруге болады, бірақ олармен ешқандай басқа операциялар орындауға болмайды.

Бұл фрагментке қатысты анықталмаған бір сұрақ қалады. Үшінші оператор үшін, фрагмент детерминделген құлығына ие болмайды деген әсер туындауы мүмкін. Шынында, егер «y = a» операторы G функциясының аяқталуынан ерте орындалса, онда y айнымалысының мәні G функциясымен анықталады, ал егер кеш орындалса онда у айнымалысы а мәнін қабылдайды. Негізінде детерминделу қамтамасыз етілген. Осы оператор орындалғаннан кейін у айнымалысының мәні әрқашан а мәніне тең болады. «y = a» операторын өңдеу алдында у айнымалысы бұғатталады.

Бұдан әрі айнымалының мәнін тексеру орындалады, егер мәні дайын емес болса, онда күтілетін мәнді қабыл алмау ұсынылады және жабдықтаушымен байланыс үзіледі. Біздің жағдайда бұл қабылдамау G функциясының орындалуынан шығатын мән. Барлық тексерістерден және оператордың орындалуынан кейін айнымалы бұғаттаудан босатылады. Мұндай тізбек бағдарлама құлығының детерминделгенінің кепілін бере алады және де әдеттегідей семантиканы қамтамасыз етеді: y = a орындалғаннан кейін у мәні а мәніне тең болады.

Жаңа кілттік сөздер қосылғаннан кейінгі С тілінің диалекті, ТС деп аталады. Жаңа тіл көптеген бағдарламалаушыларға бағдарламаларды функционалды стильде жазу үшін әдеттегідей императивті жазбаны қолдануға мүмкіндік береді.

Т-жүйесінің және ТС тілінің базалық конструкцияларымен танысу үшін екі қарапайым мысал қарастырайық: Фибоначчи санының есептелуі және ағаш тәрізді деректер структурасын рекурсивті қарап шығу.

Фибоначчидің n- ші санын табу есебін қарастырайық:

Т- жүйесін қолдана отырып есепті шешу бағдарламасының мәтіні төменде көрсетілген. Жолдардың нөмірі, әрине Т-жүйесінің бөлігі болмайды. Олар бізге бұдан әрі бағдарламалардың әртүрлі конструкцияларына түсінік бергенде керек болады.

001 # include <tc.h>

003 # include <stdio.h >

004 # include <stdlib.h >

007 unsigned cfib (unsigned _n)

008 {

009 return _n < 2? _n: cfib (_n-1) + cfib (_n-2)

010 }

012 tfun viod fib (unsigned _n, tout unsigned *_res)

013{

014 if (_n <32) {

015 *_res = cfib(_n)

016 } else {

017 tval unsigned res1, res2;

018 fib (_n-1, &res1);

019 fib (_n-2, &res2);

020 *_res = res1+res2;

021 }

022 }

024 int tmain (int argc, char* argv[])

025 {

026 unsigned n;

027 tval unsigned res;

028 if (argc < 2) {

029 terrprint (

030 “Usage:\n”

031 “ gr_fib <number>\n”

032);

033 return - 1

034 }

035 n= (unsigned)atoi(argv[1]);

036 fib(n, &res);

037 (unsigned) res;

038 terrprint(“fib(%u) = %u\n”, n, rez)

039 return 0;

040 }

Бағдарламада tval кілттік сөзі көмегімен жай және дайын емес мәндерді сақтай алатын res1, res2 және resайнымалылары анықталған.

Олардың адрестері fib Т-функциясына берілген мезетте, ал ол 18,19 және 36 жолдардағы fib шақыруы, шақыру функциясының орындалуы тоқтамайды және ол ары қарай жұмысын жалғастырады. fib екінші формальды параметрінің сипатталуы tout болғандығы себепті шақырулар мезеттерінде сәйкес айнымалы res1, res2 және res «дайын емес» болады. Ол дәл сол арнайы дайын емес (даярлықсыз) мәнді қамтиды. Қашан шақырылған функция fib нәтижені есептейді және оны айнымалыға қайтарады (жол 15 болмаса 20), бұл мән жай «дайын» мәнімен алмастырылады.

«Дайын емес» айнымалыларға қатынас (олардың мәндеріне) функцияның есептеу процесін бұғаттайды. Мысалы, ол 20 –шы жолда болуы мүмкін, онда res1 және res2 айнымалыларына қатынас (обращение) тұр. 18-ші және 19-шы жолдарда res1 және res2 айнымалыларының мәндерін білу қажет етілмейді, сондықтан fib Т-функциясының екі шақыруы да бұғаттаусыз орындалатын болады, және олары есептеу параллельді жүруі мүмкін.

Бағдарлама жұмысы барысында туындаған Т-функциясы fib шақырулары (18, 19 және 36 жолдар) есептеуге дайын тәуелсіз жұмыс порцияларын қалыптастырады (параллельділік гранулалары). Барлық бөліктер (порциялар) кезекке қойылады, олардан есептеуіш орындаушы - процестер өздері үшін жұмыс алады. Бағдарламаның мәтінінде Т-функциялары кодтың потенциалды параллель фрагменттерінің үлгілерін көрсетеді. Бағдарламаның жұмысы барысында Т-функциясы нақты шақыруының нәтижесі сияқты нақты параллельді фрагменттер пайда болады және Т-жүйесімен өңделеді.

Бағдарламада 14 жолда тұрған шартты оператор 2 есепті орындайды. Бір жағынан, қандай да бір уақыт мезетінде жаңа жұмыс порцияларының құрылуын тоқтату, және соңғы қорытынды нәтижені қалыптастыруды бастау керек. Бұл мағынада мұнда жай рекурсивті функциялармен толық ұқсастық бар. Басқа жағынан, барлық қалыптасқан жұмыс бөліктері жеткілікті салмақты болулары тиіс. Кезекті бөліктің қандай да бір процеске берілуі есебінен болатын қосымша шығындарды жасыру керек, оны есептеу көлемін арттыру арқылы істеуге болады. Осы ойлардан келіп берілген жолдағы 32 тұрақтысы пайда болады.

Дегенмен, дайын емес айнымалылар Т-жүйесінде синхрондаудың негізгі құралы болады. Дайын емес айнымалыларды оқу (мәнге қатынас) және жазу (қабылдау үшін қатынас) жағдайларының, яғни ситуацияларының айтарлықтай айырмашылықтары бар:

· дайын емес айнымалы оқу барысында осындай қатынасты орындайтын есептеу процесін бұғаттау орын алады; оның күтуі, айнымалы дайын мәнді алғанға дейін жалғасады;

· жай мәнді дайын емес айнымалыға жазу барысында ол өзінің тұтынушылары үшін дайын болады, ал берілген айнымалыда ертеректе (алдында) бұғатталған процестер бұғаттау жағдайынан шығады.

Енді қашықтағы көрсеткіштермен жұмысты суреттейтін ағашты рекурсивті аралап шығу бағдарламасын қарастырайық.

001 # include <tc.h>

003 # include <stio.h>

004 # include <stlib.n>

006 struct tree {

Дата добавления: 2015-10-29