DOI: https://doi.org/10.26089/NumMet.v19r108

Реализация модели ассоциативных вычислений на GPU: библиотека базовых процедур языка STAR

Авторы

  • Т.В. Снытникова

Ключевые слова:

вертикальная обработка данных
модель ассоциативного параллельного процессора
графический ускоритель
высокопроизводительные вычисления

Аннотация

Ассоциативные (контекстно адресуемые) параллельные процессоры типа SIMD с вертикальной обработкой информации ориентированы на решение задач нечисловой обработки данных. Моделирование работы таких систем описывается с помощью абстрактной модели типа SIMD (STAR-машины). На этой модели были разработаны эффективные алгоритмы для решения многих задач на графах. Однако из-за отсутствия широко распространенных ассоциативных архитектур эти алгоритмы не могли применяться на практике. С развитием графических ускорителей появилась возможность реализовывать ассоциативные параллельные модели без существенной потери эффективности. В качестве первого этапа реализации STAR-машины на графических ускорителях в виде библиотеки на CUDA были реализованы специфические для языка STAR типы данных и простейшие операции над ними. В настоящей статье приводится эффективная реализация на GPU библиотеки стандартных процедур языка STAR. Проведено сравнение времени работы данной реализации с временем работы процедур из стандартных библиотек (STL на CPU и CUDA thrust на GPU), выполняющих эти же операции. Планируется использовать представленную реализацию STAR-машины на GPU для решения задач на графах.

Новые вычислительные технологии

Загрузки

Опубликован

2018-03-09

Выпуск

Том 19 (2018): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Т.В. Снытникова

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
просп. Лаврентьева, 6, 630090, Новосибирск
• научный сотрудник

Библиографические ссылки

  1. J. A. Rudolph, “A Production Implementation of an Associative Array Processor: STARAN,” in Proc. Fall Joint Computer Conf., Part I, Anaheim, USA, December 5-7, 1972 (ACM Press, New York, 1972), pp. 229-241.
  2. C. C. Foster, Content Addressable Parallel Processors (Reinhold, New York, 1976).
  3. K. E. Batcher, “Bit-Serial Parallel Processing Systems,” IEEE Trans. Comput. 31 (5), 377-384 (1982).
  4. L. M. Uhr, Algorithm-Structured Computer Arrays and Networks: Architectures and Processes for Images, Precepts, Models, Information (Academic, Orlando, 1984).
  5. T. Higuchi, H. Kitano, T. Furuya, et al., “IXM2: A Parallel Associative Processor for Knowledge Processing,” in Proc. 9th Nat. Conf. on Artificial Intelligence, Anaheim, USA, July 14-19, 1991 (AAAI Press, Palo Alto, 1991), Vol. 1, pp. 296-303.
  6. D. E. Smith, J. S. Hall, and K. Miyake, Rutger’s CAM2000 Chip Architecture , Technical Report LCSR-TR-196 (Rutgers University, New Brunswick, 1993).
  7. C.-H. Hsu, D. Smith, and S. Levy, Linear-C: A Data-Parallel Extension to C , Technical Report LCSR-TR-273 (Rutgers University, New Brunswick, 1996).
  8. G. Aad, E. Abat, J. Abdallah, et al., “The ATLAS Experiment at the CERN Large Hadron Collider,” J. Instr. 3 (2008).
    doi 10.1088/1748-0221/3/08/S08003
  9. A. Annovi, M. Beretta, E. Bossini, et al., “Associative Memory Design for the FastTrack Processor (FTK) at ATLAS,” in Proc. 17th IEEE-NPSS Real Time Conference, Lisbon, Portugal, May 24-28, 2010 , IEEE Press,
    doi 10.1109/RTC.2010.5750451
  10. H. Kitano, “An Implementation on the IXM2 Associative Memory,” in Speech-to-Speech Translation: A Massively Parallel Memory-Based Approach (Springer, Boston, 1994), pp. 135-155.
  11. H. Kitano, T. Higuchi, and M. Tomita, “Massively Parallel Spoken Language Processing uusing a Parallel Associative Processor IXM2,” in Proc. First Int. Conf. on Spoken Language Processing, Kobe, Japan, November 18-22, 1990 ,
    http://www.isca-speech.org/archive/icslp_1990 . Cited February 20, 2018.
  12. K. Oi, E. Sumita, O. Furuse, et al., “Real-Time Spoken Language Translation Using Associative Processors,” in Proc. Fourth Conference on Applied Natural Language Processing, Stuttgart, Germany, October 13-15, 1994 (ACL Press, Stroudsburg, 1994), pp. 101-106.
  13. A. Sh. Nepomniaschaya and M. A. Vladyko, “A Comparison of Associative Computation Models,” Programmirovanie, No. 6, 41-50 (1997) [Program. Comput. Software 23 (6), 319-324 (1997)].
  14. A. Sh. Nepomniaschaya, “Language STAR for Associative and Parallel Computation with Vertical Data Processing,” in Parallel Computing Technologies (World Scientific, Singapore, 1991), pp. 258-265.
  15. J. L. Potter, Associative Computing: A Programming Paradigm for Massively Parallel Computers (Perseus Publ., Basel, 1991).
  16. J. Potter, J. Baker, S. Scott, et al., “ASC: An Associative-Computing Paradigm,” Computer 27 (11), 19-25 (1994).
  17. A. S. Nepomniaschaya, “Solution of Path Problems Using Associative Parallel Processors,” in Proc. Int. Conf. on Parallel and Distributed Systems, Seoul, South Korea, December 10-13, 1997 (IEEE Press, New York, 1997), pp. 610-617.
  18. A. S. Nepomniaschaya and M. A. Dvoskina, “A Simple Implementation of Dijkstra’s Shortest Path Algorithm on Associative Parallel Processors,” Fundam. Inform. 43 (1-4), 227-243 (2000).
  19. A. S. Nepomniaschaya, “An Associative Version of the Bellman-Ford Algorithm for Finding the Shortest Paths in Directed Graphs,” in Lecture Notes in Computer Science (Springer, Berlin, 2001), Vol. 2127, pp. 285-292.
  20. A. S. Nepomniaschaya, “Efficient Implementation of Edmonds’ Algorithm for Finding Optimum Branchings on Associative Parallel Processors,” in Proc. 8th Int. Conf. on Parallel and Distributed Systems, Kyongju City, South Korea, June 29-29, 2001 (IEEE Press, New York, 2001),
    doi 10.1109/ICPADS.2001.934794
  21. A. S. Nepomniaschaya, “Comparison of the Prim-Dijkstra and Kraskal Algorithms on an Associative Parallel Processor,” Kibernet. Sist. Anal., No. 2, 19-27 (2000) [Cybernet. Systems Anal. 36 (2), 162-169 (2000)].
  22. A. S. Nepomniaschaya, “Representation of the Gabow Algorithm for Finding Smallest Spanning Trees with a Degree Constraint on Associative Parallel Processors,” in Lecture Notes in Computer Science (Springer, Berlin, 2001), Vol. 1123, pp. 813-817.
  23. A. S. Nepomniaschaya, “Associative Parallel Algorithms for Dynamic Edge Update of Minimum Spanning Trees,” in Lecture Notes in Computer Science (Springer, Berlin, 2003), Vol. 2763, pp. 141-150.
  24. A. Nepomniaschaya, “Associative Parallel Algorithm for Dynamic Reconstruction of a Minimum Spanning Tree After Deletion of a Vertex,” in Lecture Notes in Computer Science (Springer, Berlin, 2005), Vol. 3606, pp. 159-173.
  25. A. Sh. Nepomniaschaya, “Associative Parallel Algorithm for Dynamic Update of a Minimum Spanning Tree after Addition of a New Node to a Graph,” Kibernet. Sist. Anal., No. 2, 19-31 (2006) [Cybernet. Systems Anal. 36 (2), 162-169 (2006)].
  26. A. Nepomniaschaya, “Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors,” Fundam. Inform. 89 (2-3), 313-329 (2008).
  27. A. Nepomniaschaya, “Associative Version of the Ramalingam Decremental Algorithm for Dynamic Updating the Single-Sink Shortest-Paths Subgraph,” in Lecture Notes in Computer Science (Springer, Berlin, 2009), Vol. 5698, pp. 257-268.
  28. A. S. Nepomniaschaya, “Associative Version of the Ramalingam Algorithm for Dynamically Updating the Shortest-Path Subgraph after Inserting a New Edge into a Graph,” Kibernet. Sist. Anal., No. 3, 45-57 (2012) [Cybernet. Systems Anal. 48 (3), 358-368 (2012)].
  29. R. A. Walker, J. L. Potter, Y. Wang, and M. Wu, “Implementing Associative Processing: Rethinking Earlier Architectural Decisions,” in Proc. 15th Int. Parallel and Distributed Processing Symposium, San Francisco, USA, April 23-27, 2000 (IEEE Press, New York, 2001), pp. 2092-2100.
  30. J. L. Trahan, M. Jin, W. Chantamas, and J. W. Baker, “Relating the Power of the Multiple Associative Computing (MASC) Model to That of Reconfigurable Bus-Based Models,” J. Parallel Distrib. Comput. 70 (5), 458-466 (2010).
  31. M. Jin, “Associative Operations from MASC to GPU,” in Proc. 21st Int. Conf. on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, July 27-30, 2015 (CSREA Press, Red Hook, 2015), pp. 388-393.
  32. T. V. Snytnikova and A. Sh. Nepomniaschaya, “Solution of Graph Problems by Means of the STAR-Machine Being Implemented on GPUs,” Prikl. Diskr. Mat. 3 (33), 98-115 (2016).
  33. A. S. Nepomniaschaya, “Basic Associative Parallel Algorithms for Vertical Processing Systems,” Bull. Novosibirsk Comput. Center, No. 9, 63-77 (2009).
  34. A. S. Nepomniaschaya and M. A. Dvoskina, “A Simple Implementation of Dijkstra’s Shortest Path Algorithm on Associative Parallel Processors,” Fundam. Inform. 43 (1-4), 227-243 (2000).
  35. B. Stroustrup, The C++ Programming Language, Special Edition (Addison-Wesley, Reading, 2000; Binom, Moscow, 2012).
  36. Realeases-thrust/thrust-GitHub.
    https://github.com/thrust/thrust/releases . Cited February 20, 2018.
  37. S. Masi, Periodic Report Summary 1 - FTK (Fast Tracker for Hadron Collider Experiments) , Technical Report 324318.
    http://cordis.europa.eu/result/rcn/167746_en.html.
  38. A. Sh. Nepomniaschaya and T. V. Snytnikova, “Associative Parallel Algorithm for Dynamic Reconstruction of the Shortest Paths Tree after Insertion of a Vertex,” Bull. Novosibirsk Comput. Center, No. 24, 89-103 (2006).