Графтар: Деректер құрылымы және параллелдік мәселелер
Graph (abstract data type)
Графтар – компьютер ғылымындағы деректер түрі. Бұл математикалық граф теориясын жүзеге асырады, төбелер мен қабырғалардан тұрады. Дерек құрылымы, алгоритмдер үшін маңызды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымдағы абстрактілі дерек түрі
Abstract data type in computer science
Компьютерлік ғылымда график – математикадағы график теориясы саласындағы бағытталмаған және бағытталған график түсініктерін іске асыруға арналған абстрактілі дерек түрі. График дерек құрылымы шекті (және мүмкін өзгертілетін) төбелер жиынтығынан (сонымен қатар түйіндер немесе нүктелер деп аталады) және осы төбелердің ретсіз жұптары жиынтығынан (бағытталмаған график үшін) немесе реттелген жұптары жиынтығынан (бағытталған график үшін) тұрады. Бұл жұптар қабырғалар (немесе сілтемелер немесе сызықтар деп те аталады) деп аталады, ал бағытталған график үшін қабырғалар деп, сондай-ақ кейде жебелер немесе доғалар деп те аталады. Төбелер график құрылымының бөлігі болуы мүмкін, немесе бүтін сандық индекстермен немесе сілтемелермен көрсетілген сыртқы объектілер болуы мүмкін. График дерек құрылымы әр қабырғаға белгілі бір қабырға мәнін, мысалы, символдық белгіні немесе сандық атрибутты (құн, сыйымдылық, ұзындық және т.б.) қосуы мүмкін.
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc. ).
Жақындықтар жиынтығының тиімді бейнеленуі
Жақындық тізімі түріндегі операциялардың уақыт күрделілігін жақсарту үшін, жақын орналасқан төбелер жиынын хэш-кестелер немесе теңгерілген екілік іздеу ағаштары сияқты тиімдірек дерек құрылымдарында сақтауға болады (соңғы түріндегі бейнелеу төбелерді сызықтық реттелген жиынның элементтерімен, мысалы, бүтін сандар немесе символдар тізбегімен анықтауды талап етеді). Хэш-кестелер арқылы жақын төбелерді бейнелеу екі берілген төбе арасындағы байланысты тексеруге және қабырғаны жоюға амортизацияланған орташа уақыт күрделілігін, ал берілген x дәрежелі төбені жоюға амортизацияланған орташа уақыт күрделілігін береді. Басқа операциялардың уақыт күрделілігі мен асимптотикалық жад қажеттілігі өзгеріссіз қалады.
The time complexity of operations in the adjacency list representation can be improved by storing the sets of adjacent vertices in more efficient data structures, such as hash tables or balanced binary search trees (the latter representation requires that vertices are identified by elements of a linearly ordered set, such as integers or character strings). A representation of adjacent vertices via hash tables leads to an amortized average time complexity of to test adjacency of two given vertices and to remove an edge and an amortized average time complexity of to remove a given vertex x of degree The time complexity of the other operations and the asymptotic space requirement do not change.
Параллельді бейнелеулер
Графтық проблемаларды параллельдеу елеулі қиындықтарға толы: деректерге тәуелді есептеулер, құрылымсыз проблемалар, нашар жақындық және есептеуге қарағанда деректерге қол жеткізудің жоғары қатынасы. Параллель архитектуралар үшін қолданылатын графтық өрнектеу осы қиындықтарды шешуде маңызды рөл атқарады. Дұрыс таңдалмаған өрнектеулер алгоритмнің байланыс шығындарын қажетсіз түрде арттыруы мүмкін, бұл оның кеңейтілуін төмендетуіне әкеледі. Бұдан әрі ортақ және таратылған жад архитектуралары қарастырылады.
The parallelization of graph problems faces significant challenges: Data driven computations, unstructured problems, poor locality and high data access to computation ratio. The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its scalability. In the following, shared and distributed memory architectures are considered.
Ортақ жады
Ортақ жад моделінде, параллель өңдеу үшін қолданылатын графтардың бейнелеуі тізбекті өңдеудегідей болады, себебі ортақ жадта граф бейнелеуіне (мысалы, жабылас тізім) параллель оқуға қол жеткізу тиімді.
In the case of a shared memory model, the graph representations used for parallel processing are the same as in the sequential case, since parallel read only access to the graph representation (e. g. an adjacency list) is efficient in shared memory.
Бөлінген жады
Бөлінген жад моделінде, графтың төбелік жиынтығын жиынтарға бөлу – қалыпты тәсіл. Мұнда – қолжетімді өңдеу элементтерінің (PE) саны. Төбелік жиынтық бөліктері, сәйкес индексі бар PE-ге, сондай-ақ тиісті жиектерге таратылады. Әрбір PE-нің өзіндік субграфтық бейнесі болады, онда басқа бөліктегі соңғы нүктесі бар жиектерге ерекше назар қажет. MPI сияқты стандартты коммуникациялық интерфейстер үшін, екінші соңғы нүктеге ие PE-нің идентификаторы анықталуы керек. Таратылған граф алгоритмдеріндегі есептеулер кезінде осы жиектер арқылы ақпаратты жіберу – коммуникацияны білдіреді. Бірақ графты бөлу – NP қиын мәселе, сондықтан оны есептеу мүмкін емес. Оның орнына, келесі эвристикалар қолданылады. 1D бөлу: Әрбір процессор төбелерді және сәйкес шығатын жиектерді алады. Бұл, adjacency матрицасының қатар немесе баған бойынша декомпозициясы ретінде түсіндірілуі мүмкін. Осы бейнелеуде жұмыс істейтін алгоритмдер үшін, барлыққа-барлық (All-to-All) коммуникациялық қадамдары, сондай-ақ хабарлама буферлерінің өлшемдері қажет, себебі әрбір PE-де басқа PE-ге шығатын жиектер болуы мүмкін. 2D бөлу: Әрбір процессор adjacency матрицасының субматрицасын алады. Процессорлар тіктөртбұрыш ретінде орналасқан деп есептейік , мұнда және – әр қатардағы және бағандағы өңдеу элементтерінің саны. Содан кейін әрбір процессор өлшемі матрицасының субматрицасын алады. Бұл, матрицадағы шахматтағы үлгі ретінде визуализациялануы мүмкін.
In the distributed memory model, the usual approach is to partition the vertex set of the graph into sets Here, is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own subgraph representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like MPI, the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication. But partitioning a graph is a NP hard problem, so it is not feasible to calculate them. Instead, the following heuristics are used. 1D partitioning: Every processor gets vertices and the corresponding outgoing edges. This can be understood as a row wise or column wise decomposition of the adjacency matrix. For algorithms operating on this representation, this requires an All to All communication step as well as message buffer sizes, as each PE potentially has outgoing edges to every other PE. 2D partitioning: Every processor gets a submatrix of the adjacency matrix. Assume the processors are aligned in a rectangle , where and are the amount of processing elements in each row and column, respectively. Then each processor gets a submatrix of the adjacency matrix of dimension This can be visualized as a checkerboard pattern in a matrix.
Бірінші іздеудің ені және тереңдігі
Кеңдікке бірінші іздеу (BFS) және тереңдікке бірінші іздеу (DFS) – берілген байланысты компоненттегі барлық түйіндерді зерттеу үшін қолданылатын екі тығыз байланысты тәсіл. Екеуі де кез келген түйінден басталады, "түбір".
Breadth first search (BFS) and depth first search (DFS) are two closely related approaches that are used for exploring all of the nodes in a given connected component. Both start with an arbitrary node, the "root".