🔢 mathematics

PackSELL: A Sparse Matrix Format for Precision-Agnostic High-Performance SpMV

تقدم الورقة البحثية PackSELL، وهو تنسيق جديد للمصفوفات المتناثرة يستخدم ترميز الفرق (delta encoding) ومخطط تعبئة مدمجاً لدعم تمثيلات البيانات غير المعتمدة على دقة محددة على وحدات معالجة الرسومات (GPUs)، محققاً تسريعاً كبيراً في عمليات ضرب المصفوفات المتناثرة في المتجهات (SpMV) والمحللات الخطية المتناثرة مقارنة بالطرق الحالية مثل cuSPARSE.

المؤلفون الأصليون: Kengo Suzuki, Takeshi Iwashita

نُشر 2026-04-16

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Kengo Suzuki, Takeshi Iwashita

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك أمين مكتبة تحاول تنظيم مكتبة ضخمة وفوضوية حيث معظم أرففها فارغة. هدفك هو العثور على كتب محددة (بيانات) وتسليمها لروبوت سريع جداً (وحدة معالجة الرسومات - GPU) ليقوم بالعمل الشاق (الحسابات الرياضية).

المشكلة هي أن المكتبة كبيرة جداً لدرجة أن الروبوت يقضي وقتاً في المشي إلى الأرفف (نقل البيانات) أكثر مما يقضيه في قراءة الكتب (القيام بالرياضيات). هذا هو "عنق زجاجة الذاكرة" الذي يبطئ الحواسيب الفائقة الحديثة.

تقدم هذه الورقة البحثية طريقة جديدة لتنظيم المكتبة تسمى PackSELL. وإليك كيف تعمل، مشروحة ببساطة:

1. الطريقة القديمة: مشكلة "الرف الفارغ"

تقليدياً، تقوم المكتبات (تنسيقات المصفوفات المتفرقة) بتنظيم الكتب حسب الصفوف. إذا كان صف ما يحتوي على 5 كتب، بينما يحتوي الصف التالي على 50 كتاباً، فإن النظام غالباً ما يجبرهم على أن يبدوا بنفس الحجم للحفاظ على الترتيب. وهذا يعني ملء الأماكن الفارغة بـ "كتب وهمية" (حشو).

التشبيه: تخيل أنك تجهز حقيبة سفر. إذا كان لديك قميص صغير ومعطف ضخم، وأجبرت على وضعهما في صندوق له نفس الحجم، فستنتهي به الأمر بإضاعة الكثير من المساحة في الهواء. الروبوت سيضطر لحمل كل ذلك الهواء الفارغ، مما يبطئه.

2. الفكرة الجديدة: "التعبئة بالفرق" (خدعة السحاب)

أدرك المؤلفان، كينغو سوزوكي وتاكيشي إيشيتا، أنه في هذه المكتبات الرياضية، تكون "مواقع الكتب" (مؤشرات الأعمدة) عادةً قريبة من بعضها البعض. بدلاً من كتابة العنوان الكامل لكل كتاب، يمكنك فقط كتابة مدى المسافة التي تحركتها من الكتاب الأخير.

التشبميه: بدلاً من كتابة "الكتاب موجود في الممر 100، الرف 5"، تكتب فقط "تحرك 3 خطوات لليمين". هذا يسمى ترميز الفرق (Delta Encoding). إنه يحول عنواناً طويلاً إلى رقم صغير جداً.

3. الخدعة السحرية: "التعبئة" (Packing)

هنا تظهر براعة PackSELL. عادةً، يتم تخزين "العنوان" و"محتوى الكتاب" في صناديق منفصلة. لكن PackSELL تدمجهما معاً في صندوق واحد مخصص الحجم.

التشبيه: تخيل أنك طباخ. بدلاً من حمل صينية منفصلة للتوابل وصينية أخرى للمكونات، تقوم بخلط كمية التوابب الدقيقة داخل وعاء المكونات.
الفائدة: هذا يسمح للكمبيوتر بحمل وزن أقل. كما يسمح للطباخ بتحديد المساحة التي سيعطيها للتوابل مقابل المكونات بدقة.
- هل تحتاج إلى دقة عالية؟ أعطِ المكونات مساحة أكبر.
- هل تحتاج إلى السرعة؟ أعطِ التوابل مساحة أقل.
- الأهم من ذلك: أنت لست مقيداً بـ "أحجام الصناديق" القياسية (مثل الأرقام الحاسوبية القياسية). يمكنك صنع صناديق مخصصة تناسب وصفتك الخاصة تماماً.

4. لماذا هذا مهم: القوة الخارقة لـ "استقلال الدقة"

معظم الأنظمة الحاسوبية جامدة. فهي لا تفهم إلا الأحجام القياسية (مثل أرقام 32-بت أو 64-بت). إذا حاولت استخدام حجم غريب أو مخصص، فإن النظام يتعطل أو يتباطأ.

PackSELL تشبه المحول العالمي (Universal Adapter). يمكنها التعامل مع:

الأحجام القياسية: الأرقام المعتادة التي تستخدمها الحواسيب.
الأحجام الصغيرة: أرقام نصف الدقة (FP16) التي تكون سريعة جداً ولكنها أقل دقة.
الأحجام الغريبة: التنسيقات المخصصة التي لا توجد في الكتب المدرسية القياسية، والمصممة خصيصاً للمشكلة المطروحة.

5. النتائج: تسريع الروبوت

اختبر الباحثون هذا على كمبيوتر فائق السرعة (NVIDIA A100 GPU).

الربح: عندما استخدموا PackSELL مع أرقام "نصف الدقة"، عمل الروبوت بسرعة 1.63 مرة أسرع من أفضل طريقة قياسية حالية.
الربح السحري: الأفضل من ذلك، وجدوا "نقطة مثالية" حيث استخدموا تنسيقاً مخصصاً كان بدقة الطريقة القياسية الثقلة والبطيئة، ولكنه بسرعة الطريقة الخفيفة والسريعة.
التأثير في العالم الحقيقي: استخدموا هذا لحل مشكلات فيزيائية معقدة (مثل محاكاة تدفق الهواء أو الكهرباء). الطريقة الجديدة حلت هذه المشكلات بسرعة 2.09 مرة أسرع من الطريقة القياسية القديمة.

الملخص

فكر في PackSELL كأنها حقيبة سفر ذكية ومخصصة للبيانات.

إنها تمنعك من حمل الهواء الفارغ (تقلل هدر الذاكرة).
تسمح لك بدمج العنوان والمحتوى معاً (تعبئة القيمة بالفرق).
تتيح لك اختيار مدى حجم الحقيبة التي تحتاجها، بغض النظر عما إذا كنت تحمل ريشة أو طوبة (تدعم أي تنسيق بيانات).

من خلال جعل البيانات أخف وأكثر مرونة، يقضي "روبوت" الكمبيوتر وقتاً أقل في المشي ووقتاً أكثر في العمل، مما يؤدي إلى تسريع هائل في الأبحاث العلمية.

إليك ملخص تقني مفصل لورقة البحث بعنوان: "PACKSELL: تنسيق مصفوفة متفرقة لعمليات ضرب المصفوفات المتفرقة (SpMV) عالية الأداء والمستقلة عن الدقة".

1. بيان المشكلة

تعد عملية ضرب المصفوفة المتفرقة في المتجه (SpMV) عملية أساسية في الحوسبة العلمية، لا سيالما عند حل الأنظمة الخطية المتفرقة باستخدام طرق الفضاء الجزئي كرايلو (Krylov subspace methods). ومع تقدم الأجهزة، اتسعت الفجوة بين عرض نطاق الذاكرة (memory bandwidth) والأداء الحسابي، مما جعل عملية SpMV عملية مقيدة بالذاكرة (memory-bound).

عنق الزجاجة: يعد تقليل حركة البيانات أمراً بالغ الأهمية. وبينما يمكن لتقنيات الدقة المختلطة (باستخدام FP16 أو BF16 أو تنسيقات مخصصة) تقليل بصمة الذاكرة، فإن نوى SpMV عالية الأداء الحالية (مثل تلك الموجودة في NVIDIA cuSPARSE) مرتبطة ارتباطاً وثيقاً بتنسيقات IEEE 754 الكلاسيكية والوصول إلى الذاكرة المحاذي للبايت (byte-aligned).
القصور: تتعامل التنسيقات المتفرقة الحالية (مثل CSR وSELL وغيرها) مع تمثيل البيانات وتشفير الفهرس بشكل منفصل. وهي تفترض ضمناً أن أنواع البيانات محاذية لحدود الأجهزة (مضاعفات البايت)، مما يجعل من الصعب استخدام التنسيقات غير التابعة لمعيار IEEE أو التنسيقات ذات عدد البتات المخصص (مثل الأعداد الصحيحة 16-بت أو تنسيقات الفاصلة العائمة المخصصة) بكفاءة دون تحمل تكاليف إضافية بسبب الحشو (padding) أو المحاذاة.
الهدف: تطوير تنسيق مصفوفة متفرقة يدعم تمثيلات بيانات مستقلة عن الدقة (precision-agnostic) (بما في ذلك التنسيقات غير التابعة لمعيار IEEE) مع تقليل بصمة الذاكرة وتعظيم إنتاجية وحدة معالجة الرسومات (GPU).

2. المنهجية: تنسيق PackSELL

يقترح المؤلفون PackSELL، وهو تنسيق مصفوفة متفرقة جديد مبني على تنسيق Sliced ELLPACK (SELL). ويقدم ابتكارين جوهريين لضغط البيانات وتمكين التخصيص المرن للبتات:

أ. تشفير الفرق (Delta Encoding) لفهارس الأعمدة

بدلاً من تخزين فهارس الأعمدة المطلقة، يقوم PackSELL بتخزين الفرق (delta) بين فهرس العمود الحالي والعنصر غير الصفري السابق في نفس الصف.

للصف $i$ ، يتم تشفير فهرس العمود $j$ لعنصر غير صفري كـ $d_{i,j} = j - \max(S_{i,j})$ ، حيث $S_{i,j}$ هي مجموعة فهارس الأعمدة السابقة.
يستغل هذا التغيير خاصية الموضعية (locality) للعناصر غير الصفرية، مما ينتج عنه غالباً أعداد صحيحة صغيرة تتطلب بتات أقل من الفهارس الكاملة 32-بت.

ب. تعبئة الفرق والقيمة (Delta–Value Packing)

يقوم PackSELL بتعبئة الفرق (delta) وقيمة المصفوفة في كلمة واحدة بسعة $W$ -بت (عادةً $W=32$ ).

الهيكل: تتكون الكلمة من عدد صحيح غير سالب بسعة $D$ -بت للفرق، و $V$ بت للقيمة، وبت واحد للعلامة (flag) ( $W = V + D + 1$ ).
آلية العلامة (Flag Mechanism):
- العلامة = 1: الفرق يتناسب مع $D$ -بت. يتم تخزين القيمة (باستخدام أي تنسيق $V$ -بت، بما في ذلك التنسيقات غير التابعة لـ IEEE) في الـ $V$ بت العليا، ويتم إزاحة الفرق (delta) بمقدار بت واحد لليسار.
- العلامة = 0: الفرق يتجاوز $D$ -بت (تجاوز السعة/overflow). تُستخدم جميع الـ $W-1$ بت لتخزين الفرق الكبير (المُزاح لليسار). وتصبح قيمة المصفوفة صفراً فعلياً.
التعامل مع تجاوز السعة (العناصر الوهمية/Dummy Elements): عندما يكون الفرق أكبر من أن يستوعبه $D$ -بت، يقوم PackSELL بإدراج عنصر وهمي عند فهرس العمود المستهدف. يحمل هذا العنصر الوهمي الفرق الكبير (Flag=0)، ويتبع ذلك العنصر غير الصفري الفعلي بفرق قدره 0 (Flag=1). يسمح هذا بإبقاء $D$ صغيراً جداً (على سبيل المثال 1 بت) لزيادة $V$ (دقة القيمة) إلى أقصى حد دون فقدان القدرة على التمثيل.
المرونة: من خلال ضبط النسبة بين $D$ و $V$ ، يمكن للمستخدمين تحديد تنسيقات بيانات مخصصة. على سبيل المثال، يمكن تخصيص 8 بت للأس و 22 بت للمانتيسيا (E8M22) أو استخدام FP16 القياسي (16 بت) مع 15 بت للفرق.

ج. تفاصيل التنفيذ

المحاذاة (Alignment): يحافظ PackSELL على هيكل SELL عبر تقسيم الصفوف إلى كتل بحجم $C$ (مثلاً 32) لضمان تجانس عبء العمل والوصول المتماسك للذاكرة (coalesced memory access).
تبديل الصفوف (Row Permutation): لتقليل الحشو، يتم إعادة ترتيب الصفوف داخل كتل مكونة من $\sigma$ من الصفوف (SELL-C-$\sigma). يتعامل PackSELL مع ذلك ضمنياً باستخدام مصفوفة تبديل (permutation array).
فك التعبئة (Unpacking): تم تصميم عملية فك التعبئة لتكون خالية من التفرع (branch-free) على وحدات معالجة الرسومات، وذلك باستخدام عمليات البت لاستخراج العلامة، ومقادير الإزاحة، والقيم بكفاءة.

3. المساهمات الرئيسية

تنسيق مبتكر (PackSELL): تنسيق مصفوفة متفرقة يضغط الفهارس والقيم معاً، مما يتيح دعم عروض بتات عشوائية وتنسيقات فاصلة عائمة غير تابعة لمعيار IEEE.
تصميم مستقل عن الدقة (Precision-Agnostic Design): القدرة على المقايضة بين دقة الفهرس ( $D$ ) ودقة القيمة ( $V$ ) ديناميكياً، مما يسمح لنفس النواة (kernel) بتشغيل FP16 أو تنسيقات E8 مخصصة أو حتى تمثيلات قائمة على الأعداد الصحيحة.
تحليل الأداء: تقييم شامل لأنوية SpMV القائمة على PackSELL وتكاملها في طرق كرايلو ذات الدقة المختلطة (F3R و Inner-Outer CG).
تحديد السيناريوهات: إثبات سيناريو عملي حيث تتفوق التنسيقات غير التابعة لـ IEEE (تحديداً متغيرات E8M) على مناهج FP16/FP32 القياسية من حيث السرعة والدقة.

4. النتائج التجريبية

أُجريت التجارب على وحدة معالجة الرسومات NVIDIA A100 باستخدام 435 مصفوفة من مجموعة SuiteSparse.

أ. أداء SpMV المستقل

أداء FP16: بالنسبة للمصفوفات ذات أنماط التفرع المنتظمة (292 من أصل 435 مصفوفة)، تفوق PackSELL (المعدل بـ $D=15, V=16$ ) على نواة SELL الخاصة بـ NVIDIA cuSPARSE بما يصل إلى 1.63 ضعف. كما تفوق بشكل كبير على cuCSR و DASP.
التنسيقات غير التابعة لـ IEEE: باستخدام تنسيقات E8M مخصصة (مثلاً $D=1, V=21$ )، حقق PackSELL دقة بمستوى FP32 (خطأ خلفي منخفض) مع الحفاظ على أداء يقارب أو يتجاوز أداء FP16 في cuSPARSE.
بصمة الذاكرة: قلل PackSELL استخدام الذاكرة بنسبة تصل إلى ~25% مقارنة بـ SELL القياسي للمصفوفات الكثيفة، مقترباً من الحد الأدنى النظري البالغ 0.75 (32 بت إجمالي / 48 بت لـ فهرس 32-بت + قيمة 16-بت).

ب. طرق الفضاء الجزئي (Solvers)

حل F3R (الممكن بـ FP16): أدى دمج PackSELL في حل F3R (الذي يستخدم FP16 SpMV في الطبقات الداخلية) إلى تسريع قدره 1.32 ضعف مقارم بـ تنفيذ F3R القياسي بـ FP16، مع تسريع يصل إلى 2.64 ضعف مقارنة بحلول FP64 الكاملة.
الخوارزمية المتداخلة (Inner-Outer CG):
- غالباً ما فشلت خوارزمية FP16-IO-CG القياسية في التقارب أو تطلبت تكرارات مفرطة بسبب فقدان الدقة.
- E8MY-IO-CG: باستخدام PackSELL مع تنسيق مخصص (مثلاً $D=10, V=14$ )، حقق الحل دقة بمستوى FP32 مع العمل بسرعة أكبر من نوى FP32.
- حقق هذا النهج تسريعاً قدره 2.09 ضعف مقارنة بـ PCG القياسي كامل الدقة (FP64)، مقترباً من المكسب المثالي النظري البالغ 2.0 ضعف.

5. الأهمية والأثر

كسر حاجز المحاذاة: يفك ارتباط PackSELL بين تمثيل البيانات وقيود محاذاة الأجهزة، مما يثبت إمكانية تنفيذ التنسيقات غير المحاذية للبايت وغير التابعة لـ IEEE بكفاءة على وحدات معالجة الرسومات.
تمكين الدقة المختلطة المتقدمة: يوفر مساراً عملياً لاستخدام تنسيقات الفاصلة العائمة المخصصة في الحلول التكرارية، مما يحل مشكلة "الدقة مقابل السرعة" التي تعيق مناهج FP16/BF16 القياسية.
جاهزية المستقبل: مع تطور الأجهزة مع وجود المزيد من الوحدات المتخصصة ذات الدقة المنخفضة، يقدم PackSELL إطاراً مرناً لاستغلال هذه الوحدات دون الحاجة لإعادة كتابة البنية التحتية الكاملة للمصفوفات المتفرقة.
المنفعة العملية: تظهر النتائج أنه بالنسبة لمجموعة كبيرة من المصفوفات الواقعية، فإن PackSELL ليس مجرد تحسين نظري بل هو أداة عملية لتسريع المحاكاة العلمية.

في الختام، يمثل PackSELL خطوة مهمة للأمام في الجبر الخطي المتفرق من خلال توحيد ضغط الفهارس وتعبئة القيم، مما يفتح آفاق الأداء العالي لمجموعة أوسع من تمثيلات البيانات.