Published September 24, 2017
| Version v1
Publication
Open
A Non-Speculative Parallelization of Reverse Cuthill-McKee Algorithm for Sparse Matrices Reordering
- 1. Universidade Federal do Espírito Santo
Description
This work presents a new parallel non-speculative implementation of the Unordered Reverse Cuthill-McKee algorithm.Reordering quality (bandwidth reduction) and reordering performance (CPU time) are evaluated in comparison with a serial implementation of the algorithm made available by the state-of-the-art mathematical software library HSL.The bandwidth reductions reached by our parallel RCM were more than 90% for several large matrices out of the ones tested, and the time reordering improvement was up to 57.82%.Speedups higher than 3.0X were achieved with the parallel RCM.The underlying parallelism was supported by the OpenMP framework and three strategies for reducing idle threads were incorporated into the algorithm.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
يقدم هذا العمل تنفيذًا موازيًا جديدًا غير مضارب لخوارزمية Cuthill - McKee العكسية غير المرتبة. يتم تقييم جودة إعادة الترتيب (تقليل عرض النطاق الترددي) وأداء إعادة الترتيب (وقت وحدة المعالجة المركزية) مقارنةً بالتنفيذ التسلسلي للخوارزمية التي توفرها مكتبة البرامج الرياضية الحديثة HSL. كانت تخفيضات عرض النطاق الترددي التي توصلت إليها آلية التنسيق الإقليمية المتوازية الخاصة بنا أكثر من 90 ٪ للعديد من المصفوفات الكبيرة من تلك التي تم اختبارها، وكان الوقت الذي تم فيه تحسين إعادة الترتيب يصل إلى 57.82 ٪. تم تحقيق سرعات أعلى من 3.0X باستخدام آلية التنسيق الإقليمية المتوازية. تم دعم التوازي الأساسي من خلال إطار OpenMP وتم دمج ثلاث استراتيجيات لتقليل الخيوط الخاملة في الخوارزمية.Translated Description (French)
Ce travail présente une nouvelle implémentation parallèle non spéculative de l'algorithme Unordered Reverse Cuthill-McKee. La qualité de l'ordre (réduction de la bande passante) et les performances de réordonnancement (temps CPU) sont évaluées par rapport à une implémentation en série de l'algorithme mis à disposition par la bibliothèque logicielle mathématique de pointe HSL.Les réductions de bande passante atteintes par notre RCM parallèle ont été supérieures à 90% pour plusieurs grandes matrices parmi celles testées, et l'amélioration du réordonnancement temporel a atteint 57,82%. Des vitesses supérieures à 3,0X ont été atteintes avec le RCM parallèle. Le parallélisme sous-jacent a été pris en charge par le cadre OpenMP et trois stratégies de réduction des threads inactifs ont été incorporées dans l'algorithme.Translated Description (Spanish)
Este trabajo presenta una nueva implementación paralela no especulativa del algoritmo Cuthill-McKee inverso desordenado. La calidad del reordenamiento (reducción del ancho de banda) y el rendimiento del reordenamiento (tiempo de CPU) se evalúan en comparación con una implementación en serie del algoritmo disponible mediante la biblioteca de software matemático de última generación HSL.Las reducciones del ancho de banda alcanzadas por nuestro RCM paralelo fueron más del 90% para varias matrices grandes de las probadas, y la mejora del reordenamiento del tiempo fue de hasta el 57,82%. Se lograron aceleraciones superiores a 3,0X con el RCM paralelo. El paralelismo subyacente fue respaldado por el marco OpenMP y se incorporaron tres estrategias para reducir los subprocesos inactivos en el algoritmo.Files
179.pdf.pdf
Files
(265.8 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:66c1c884917a25b85d65b1f12d0b96e4
|
265.8 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- موازاة غير مضاربة لخوارزمية Cuthill - McKee العكسية لإعادة ترتيب المصفوفات المتفرقة
- Translated title (French)
- A Non-Speculative Parallelization of Reverse Cuthill-McKee Algorithm for Sparse Matrices Reordering
- Translated title (Spanish)
- Una paralelización no especulativa del algoritmo inverso de Cuthill-McKee para el reordenamiento de matrices dispersas
Identifiers
- Other
- https://openalex.org/W2760185815
- DOI
- 10.15439/2017f179
References
- https://openalex.org/W1988888548
- https://openalex.org/W2007152167
- https://openalex.org/W2035080386
- https://openalex.org/W2046140068
- https://openalex.org/W2053087839
- https://openalex.org/W2086268861
- https://openalex.org/W2097717378
- https://openalex.org/W2116603646
- https://openalex.org/W2152907584
- https://openalex.org/W2157807901
- https://openalex.org/W3007272028
- https://openalex.org/W4206566500
- https://openalex.org/W4232836277
- https://openalex.org/W85690038