библиотека

собственные статьи и публикации

1. Тезисы доклада "Исследование методов разбиения графов большой размерности со многими ограничениями при параллельной работе (система ParMETIS, hMETIS, METIS)".
   Авторы: Шелест Л.Н., Костин В.И.
   Тезисы доклада на третьей международной научно-технической конференции молодых ученых и студентов "ИНФОРМАТИКА И КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ 2007", посвященная 75-летию Донецкой области, которая будет проходить 11-13декабря 2007 года в ДонНТУ. В работе рассмотрены методы разбиения графов большой размерности со многими ограничениями, которые используются в пакетах METIS, ParMETIS и hMETIS.

2. Организация хранения данных при разбиении графов методом бисекции.
   Авторы: Костин В.И., Краснокутская М.В.
   Науковi працi Донецького нацiонального технiчного унiверситету. Серiя "Iнформатика, кiбернетика i обчислювана технiка" (ИКОТ-2007). Випуск 8 (120) - Донецьк: ДонНТУ, 2007. - 343 с. "Организация хранения данных при разбиении графов методом бисекции", стр. 151-159.
   
   
3. Моделирование распараллеливания задачи с помощью графа потоков данных. (64 Kb)
   Авторы: Костин В.И., Краснокутская М.В.
   Доклад на I Республиканской научной конференции студентов, аспирантов и молодых ученых "КОМПЬЮТЕРНЫЙ МОНИТОРИНГ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ", ДонНТУ, май 2005 г. В докладе описывается представление распараллеливаемой задачи с помощью графа потоков данных. Уравновешивание вычислительной загрузки между процессорами можно отразить на задаче разбиения графа. Предлагается два алгоритма решения этой задачи - Kernighan-Lin / Fiduccia-Mattheyses (KL/FM), алгоритм спектральной бисекции. Описываются некоторые особенности их применения к графам с большим числом вершин.
   
   
4. Исследование методов организации данных в задачах разбиения графов больших размерностей. (99 Kb)
   Авторы: Краснокутская М.В., Костин В.И.
   Исследование методов организации данных в задачах разбиения графов больших размерностей. "ИНФОРМАТИКА И КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ 2005". Сборник трудов первой международной студенческой научно-технической конференции. ДонНТУ, 2005. Тезисы доклада на первой международной студенческой научно-технической конференции "ИНФОРМАТИКА И КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ 2005", которая проходила 15 декабря 2005 года в ДонНТУ.

5. George Karypis, Vipin Kumar. Multilevel Algorithms for Multi-Constraint Graph Partitioning. University of Minnesota, Department of Computer Science / Army HPC Research Center. Minneapolis, MN 55455. Technical Report # 98-019.
   
   
6. George Karypis. Vipin Kumar. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0. - University of Minnesota: September 20, 1998.
   
   
7. G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998 (to appear). Also available on WWW at URL http://www.cs.umn.edu/?karypis. A short version appears in Intl. Conf. on Parallel Processing 1995. В этой статье рассматривается многофазное разбиение нерегулярных графов.
   
   
8. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998. Also available on WWW at URL http://www.cs.umn.edu/?karypis. Журнал о параллельном распределении вычислений. В этой статье рассматривается k-фазное разбиение нерегулярных графов.
   
   
9. Bruce Hendrickson and Robert Leland. The chaco user's guide, version 1.0. Technical Report SAND93-2339, Sandia National Laboratories, 1993.
   
   
10. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970. Статья рассматривает эффективность эвристической процедуры для разбиения графов. Технический журнал Bell System.
    
    
11. C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982. Линейная временная эвристика для усовершенствования сетевого разделения.
    
    
12. Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.
    
    
13. George Karypis, Vipin Kumar. Multilevel k-way Hypergraph Partitioning. - Department of Computer Science & Engineering; Army HPC Research Center; University of Minnesota, Minneapolis, MN 55455. Technical Report #98-036. Эта статья рассматривает k-фазное разбиение графов.
    
    
14. Charles J. Alpert and Andrew B. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1-81, 1995.
    
    
15. C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.
    
    
16. L. A. Sanchis. Multiple-way network partitioning. IEEE Transactions on Computers, pages 62-81, 1989.
    
    
17. George Karypis, Kirk Schloegel and Vipin Kumar. PARMETIS Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3.0. - University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN 55455: March 28, 2002. Перевод части статьи.
    
    
18. George Karypis, Vipin Kumar. Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs. - University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, Technical Report: 96-036.
    
    
19. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1053, 1986.
    
    
20. A. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, 10:345-363, 1973. В данной работе были рассмотрены алгоритмы разбиения графов и определения собственных значений. Рассматривались особенности их реализации для графов больших размерностей. Были проанализированы два способа организации данных для представления разреженных матриц больших размеров. Была разработана программная реализация этих двух способов, построены диаграммы зависимости времени умножения матрицы на вектор от размерности матрицы и степени ее разреженности.
    
    
21. Kirk Schloegel, George Karypis, Vipin Kumar. Graph Partitioning for High Performance Scientific Simulations.University of Minnesota, Department of Computer Science, Minneapolis, 2000. Also available on WWW at URL http://citeseer.ist.psu.edu/schloegel00graph.html. В статье представлен краткий обзор алгоритмов, разбивающих графы, используемые для научных моделирований на высокопроизводительных параллельных компьютерах.

22. Дискретная математика. Основные тезисы. (260 Kb)
    Авторы: Кирсанов М.Н., Показеев В.В.
    Дискретная математика. Основные тезисы. Кирсанов М.Н. МЭИ (ТУ), Показеев В.В. МГТУ "МАМИ".

23. Graph Partitioning Algorithms for DistributingWorkloads of Parallel Computations, 1998 (340 Kb)
    Авторы: Bradford L. Chamberlain.
    Also available on WWW at URL http://www.cs.washington.edu/homes/brad/cv/pubs/degree/generals.html. Эта статья рассматривает алгоритмы разбиения графа, используемые для параллельного вычисления. Кроме того, описываются многоуровневые методы разделения и вопросы связанные с параллельным разделением. Все алгоритмы оценены качественно по их скорости выполнения и способности генерировать разделение с маленькими разделителями.
    
    
24. Быстрый высокопроизводительный алгоритм для разделения нерегулярных графов. (450 Kb)
    Авторы: Бувайло Д.П., Толок В.А.
    Быстрый высокопроизводительный алгоритм для разделения нерегулярных графов. Вiсник Запорiзького державного унiверситету № 2, 2002. http://www.zsu.zp.ua/herald/articles/2612.pdf (439 Kb). В этой статье представлены многоуровневые методы разбиения графов и их применение к графам больших размеров, возникающих в различных прикладных областях. Описывается несколько различных применяемых комбинаций эвристик для всех трех стадий: огрубление, разделение самого грубого графа, восстановление.