115
айналдыруға болады. Бұл үшін операциялар орындалуының тек аяқталған
кезеңін ғана емес, сонымен қатар басталған кезеңін де белгілейміз.
Параллельді түрдің ярустарын келесі тәсілмен тұрғызамыз.
Кіру доғалары жоқ және орындалуының мезгілдік интервалының бос
емес қиылысуы бар операцияларына сәйкес келетін шыңдардың максималды
санын бірінші ярусқа біріктіреміз. Бұл шыңдар алдын ала бір-бірімен
ешқандай доғалармен байланыспаған. Алгоритм графынан бірінші ярус
шыңдары мен оларға қатысты доғаларды алып тастаймыз. Графтың қалған
бӛлігіне ұқсас келетін шыңдар тобын бӛлеміз де, оны параллель түрдің
екінші ярусы деп санайтын боламыз және т.б.
Сонымен, әртүрлі компьютерлерде бір ғана алгоритмнің түрлі жолмен
орындалуы және алгоритм графының әртүрлі параллельді түрлерінің
арасында белгілі бір ӛзара сәйкестік бар екені кӛрінеді. Алгоритм графы
және оның параллельді түрлерін біле отырып, алгоритмдегі параллельділік
қорының қаншалықты екенін және оны параллельді архитектуралы нақты бір
компьютерде қалай жақсы іске асыруға болатынын түсінуге болады. Міне,
сол себепті де біз алгоритм графының тұрғызылуына және оның параллельді
түрлерін табуға кӛп кӛңіл бӛлудеміз.
Әрі қарай, алгоритмнің параллельді формасы, алгоритм ярустары,
алгоритмнің параллельді түрінің биіктігі туралы айта отырып, алгоритм
графының параллельді түрлеріне қатысты терминологияны алгоритмнің ӛзіне
де жиі қолданып отыратын боламыз. Алгоритмнің параллельді түрлерінің
минималды биіктігін -
алгоритм биіктігі деп атайтын боламыз және т.б.
Басқаша айтқанда, бірден алгоритмнің операцияларын-граф шыңдары деп, ал
операциялар арасындағы жартылай реттілік қатынастарын – иіндер (доғалар)
деп санайтын боламыз. Бұл негізінен ешқандай жаңа білім бермейді,
дегенмен «алгоритм графының шыңдарының мынадай жиынтығына сәйкес
келетін операциялар жиынтығы» деген сияқты кӛп құрамды ұзақ сӛздер
тізбегін алып тастау арқылы шытырман фразалардан құтылуға мүмкіндік
береді. Алгоритм графының қарапайым түрін түрлі-түсті суреттер мен
сызбаларда қолданған әлдеқайда ыңғайлы.
Ал енді, компьютерде алгоритмнің қай параллельді түрі орындалып
жатқанына қарамастан, орындалу нәтижесі бәрібір бірдей болатынын
кӛрсетейік.
Достарыңызбен бөлісу: