Հրապարակման մանրամասներ:

Լույս է տեսնում 1948 թվականից՝ տարին 4 անգամ։

Ամսագրի կամ հրապարակման վերնագիր:

ՀՀ ԳԱԱ և ՀՊՃՀ Տեղեկագիր. Տեխնիկական գիտություններ =Proceedings of the NAS RA and SEUA: Technical Sciences

Հրապարակման ամսաթիւ:

2025

Հատոր:

78

Համար:

1

ISSN:

0002-306X

Պաշտոնական URL:

Լրացուցիչ տեղեկութիւն:

Հարությունյան Ա. Գ., Խաչատրյան Ռ. Ն., Арутюнян А. Г., Хачатрян Р. Н.

Այլ վերնագիր:

Կմախքային գրաֆի կառուցման ալգորիթամի խոշորահատիկ զուգահեռացումը ; Крупнозернистая параллелизация алгоритма построения каркасного графа

Աջակից(ներ):

Պատ․ խմբ․՝ Ա․ Գ․ Նազարով (1957-1964) ; Մ․ Վ․ Կասյան (1964-1988) ; Ռ․ Մ․ Մարտիրոսյան (1989-2017 ) ; Գլխավոր խմբ․՝ Վ․ Շ․ Մելիքյան (2018-)

Ծածկոյթ:

121-129

Ամփոփում:

The spanning graph construction problem is to create a sparse graph over a given set of points so that the graph contains at least one minimum spanning tree under a specified distance metric. This problem is the basis for many algorithms like rectilinear minimum spanning tree construction, efficient Steiner tree construction, obstacle aware Steiner tree construction, etc. These algorithms are used in many fields of computer science, especially in VLSI routing. As many of these algorithms are NP-complete problems and some of them use the spanning graph construction approach, parallelization of the spanning graph construction algorithm will optimize other problems as well. In this paper, we present the coarse-grained parallelization approach of the spanning graph construction algorithm. The proposed algorithm, compared to the existing sequential algorithm, achieves an average performance improvement of about 40-60% and keeps the correctness of the original algorithm.
Տրված կետերի բազմության վրա որոշված մետրիկայով նոսր գրաֆ կառուցելու խնդիրը, որը պարունակում է առնվազն մեկ նվազագույն կմախքային ծառ, կոչվում է կմախքային գրաֆի կառուցման խնդիր։ Այս խնդիրը հիմք է հանդիսանում մի շարք ալգորիթմների համար, ինչպիսիք են ուղղանկյուն նվազագույն կմախքային ծառի կառուցումը, Սթայների ծառի արդյունավետ կառուցումը, խոչընդոտներից խուսափող Սթայների ծառի կառուցումը և այլն։ Այս ալգորիթմները կիրառվում են համակարգչային գիտության բազմաթիվ ոլորտներում, հատկապես՝ ծրագծման ալգորիթմներում։ Քանի որ այս խնդիրներից շատերը NP-լրիվ են, և դրանցից մի քանիսը օգտագործում են կմախքային գրաֆի կառուցման մոտեցումը, ապա այդ պրոցեսի զուգահեռացումը կարող է օպտիմալացնել նաև մյուս խնդիրները։ Ներկայացվում է կմախքային գրաֆի կառուցման ալգորիթմի բարձր մակարդակի զուգահեռացման մոտեցումը։ Առաջարկվող ալգորիթմը, համեմատած առկա հաջորդական տարբերակի հետ, ապահովում է միջինում մոտավորապես 40-60% արտադրողականության աճ։
Задача построения каркасного графа заключается в создании разреженного графа на заданном множестве точек таким образом, чтобы граф содержал хотя бы одно минимальное остовное дерево в соответствии с заданной метрикой расстояния. Эта задача лежит в основе множества алгоритмов, таких как построение прямоугольного минимального остовного дерева, эффективное построение дерева Штайнера, построение дерева Штайнера с учетом препятствий и др. Эти алгоритмы применяются во многих областях информатики, особенно в алгоритмах трассировки в проектировании VLSI. Поскольку многие из этих задач являются NP-полными и некоторые из них используют подход построения каркасного графа, параллелизация этого этапа может также оптимизировать и другие задачи. В данной работе представлен подход к высокоуровневой параллелизации алгоритма построения каркасного графа. Предлагаемый алгоритм, по сравнению с существующим последовательным вариантом, обеспечивает в среднем около 40…60% прироста производительности.

Հրատարակութեան վայրը:

Երևան

Հրատարակիչ:

«Պոլիտեխնիկ» տպ.

Ձեւաչափ:

pdf

Նոյնացուցիչ:

oai:arar.sci.am:427647

Դասիչ:

АЖ 413

Թուայնացում:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Բնօրինակին գտնուելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան