2025-11-18T22:43:13.755250

Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms

Mukunoki, Ozaki
To obtain accurate results in numerical computation, high-precision arithmetic is a straightforward approach. However, most processors lack hardware support for floating-point formats beyond double precision (FP64). Double-word arithmetic (Dekker 1971) extends precision by using standard floating-point operations to represent numbers with twice the mantissa length. Building on this concept, various multi-word arithmetic methods have been proposed to further increase precision by combining additional words. Simplified variants, known as quasi algorithms, have also been introduced, which trade a certain loss of accuracy for reduced computational cost. In this study, we investigate the performance of quasi algorithms for double- and triple-word arithmetic in sparse iterative solvers based on the Conjugate Gradient method, and compare them with both non-quasi algorithms and standard FP64. We evaluate execution time on an x86 processor, the number of iterations to convergence, and solution accuracy. Although quasi algorithms require appropriate normalization to preserve accuracy - without it, convergence cannot be achieved - they can still reduce runtime when normalization is applied correctly, while maintaining accuracy comparable to full multi-word algorithms. In particular, quasi triple-word arithmetic can yield more accurate solutions without significantly increasing execution time relative to double-word arithmetic and its quasi variant. Furthermore, for certain problems, a reduction in iteration count contributes to additional speedup. Thus, quasi triple-word arithmetic can serve as a compelling alternative to conventional double-word arithmetic in sparse iterative solvers.
academic

উচ্চ-নির্ভুলতা পাটিগণিত সহ প্রায় বহু-শব্দ অ্যালগরিদম ব্যবহার করে বিরল পুনরাবৃত্তিমূলক সমাধানকারী

মৌলিক তথ্য

  • গবেষণাপত্র ID: 2510.13536
  • শিরোনাম: Sparse Iterative Solvers Using High-Precision Arithmetic with Quasi Multi-Word Algorithms
  • লেখক: Daichi Mukunoki (নাগোয়া বিশ্ববিদ্যালয়), Katsuhisa Ozaki (শিবাউরা প্রযুক্তি প্রতিষ্ঠান)
  • শ্রেণীবিভাগ: cs.MS (গাণিতিক সফটওয়্যার)
  • প্রকাশনার সময়: ২০২৫ সালের ১৫ অক্টোবর (arXiv প্রাক-প্রকাশনা)
  • গবেষণাপত্র লিঙ্ক: https://arxiv.org/abs/2510.13536

সারসংক্ষেপ

সংখ্যাগত গণনায় নির্ভুল ফলাফল পাওয়ার জন্য উচ্চ-নির্ভুলতা পাটিগণিত একটি সরাসরি পদ্ধতি। তবে বেশিরভাগ প্রসেসরে দ্বিগুণ-নির্ভুলতা (FP64) ছাড়া অন্যান্য ফ্লোটিং-পয়েন্ট ফরম্যাটের জন্য হার্ডওয়্যার সহায়তা নেই। দ্বিশব্দ পাটিগণিত (Dekker 1971) মান ফ্লোটিং-পয়েন্ট অপারেশন ব্যবহার করে দ্বিগুণ মন্টিসা দৈর্ঘ্য সহ সংখ্যা প্রতিনিধিত্ব করে নির্ভুলতা প্রসারিত করে। এই ধারণার উপর ভিত্তি করে, বিভিন্ন বহু-শব্দ পাটিগণিত পদ্ধতি প্রস্তাব করা হয়েছে যা অতিরিক্ত শব্দ সংযোজন করে নির্ভুলতা আরও বৃদ্ধি করে। সরলীকৃত বৈকল্পিক, অর্থাৎ প্রায় অ্যালগরিদম, নির্ভুলতার নির্দিষ্ট ক্ষতির বিনিময়ে গণনা খরচ হ্রাস করার জন্য প্রবর্তিত হয়েছে। এই গবেষণা সংযুক্ত গ্রেডিয়েন্ট পদ্ধতির উপর ভিত্তি করে বিরল পুনরাবৃত্তিমূলক সমাধানকারীতে দ্বিশব্দ এবং ত্রিশব্দ পাটিগণিতের প্রায় অ্যালগরিদম কর্মক্ষমতা অনুসন্ধান করে এবং এটিকে অ-প্রায় অ্যালগরিদম এবং মান FP64 এর সাথে তুলনা করে।

গবেষণা পটভূমি এবং প্রেরণা

মূল সমস্যা

  1. হার্ডওয়্যার সীমাবদ্ধতা সমস্যা: বেশিরভাগ প্রসেসরে দ্বিগুণ-নির্ভুলতা (FP64) ছাড়া অন্যান্য ফ্লোটিং-পয়েন্ট ফরম্যাটের জন্য হার্ডওয়্যার সহায়তা নেই, যা উচ্চ-নির্ভুলতা সংখ্যাগত গণনার বাস্তবায়ন সীমিত করে
  2. বিরল পুনরাবৃত্তিমূলক সমাধানকারীর নির্ভুলতা প্রয়োজনীয়তা: বড় বিরল রৈখিক সিস্টেম সমাধান করার সময়, রাউন্ডিং ত্রুটি সংমিশ্রণের জন্য প্রয়োজনীয় পুনরাবৃত্তির সংখ্যা বৃদ্ধি করে, যা সমাধান নির্ভুলতা এবং দক্ষতা প্রভাবিত করে
  3. কর্মক্ষমতা এবং নির্ভুলতার মধ্যে ভারসাম্য: ঐতিহ্যবাহী বহু-শব্দ পাটিগণিত পদ্ধতি নির্ভুলতা উন্নত করতে পারে কিন্তু গণনা ওভারহেড বেশি

গবেষণার গুরুত্ব

  • বিরল পুনরাবৃত্তিমূলক সমাধানকারী বৈজ্ঞানিক গণনা এবং প্রকৌশল প্রয়োগে ব্যাপকভাবে ব্যবহৃত হয়
  • উচ্চ-নির্ভুলতা পাটিগণিত সংমিশ্রণ উন্নত করতে এবং পুনরাবৃত্তির সংখ্যা হ্রাস করতে পারে
  • স্মৃতি-সীমিত প্রয়োগে, বহু-শব্দ পাটিগণিতের অতিরিক্ত ওভারহেড স্মৃতি বিলম্ব দ্বারা মুখোশ করা যেতে পারে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  • ঐতিহ্যবাহী বহু-শব্দ পাটিগণিত (যেমন DW, TW) উচ্চ গণনা খরচ
  • প্রায় অ্যালগরিদম গণনা খরচ হ্রাস করে কিন্তু নির্ভুলতা হ্রাস করতে পারে
  • পুনরাবৃত্তিমূলক সমাধানকারীতে প্রায় অ্যালগরিদম কর্মক্ষমতার সিস্টেমেটিক মূল্যায়নের অভাব

মূল অবদান

  1. প্রায় অ্যালগরিদম কর্মক্ষমতার সিস্টেমেটিক মূল্যায়ন: বিরল পুনরাবৃত্তিমূলক সমাধানকারীতে QDW এবং QTW অ্যালগরিদমের কর্মক্ষমতা প্রথমবার সিস্টেমেটিকভাবে মূল্যায়ন করা
  2. স্বাভাবিকীকরণের মূল ভূমিকা আবিষ্কার: প্রায় অ্যালগরিদম সংমিশ্রণের জন্য উপযুক্ত স্বাভাবিকীকরণের গুরুত্ব প্রমাণ করা
  3. QTW কে কার্যকর বিকল্প হিসাবে প্রস্তাব: প্রমাণ করা যে প্রায় ত্রিশব্দ পাটিগণিত (QTW) ঐতিহ্যবাহী দ্বিশব্দ পাটিগণিতের কার্যকর বিকল্প হতে পারে
  4. ব্যাপক কর্মক্ষমতা বিশ্লেষণ: সম্পাদন সময়, পুনরাবৃত্তির সংখ্যা এবং সমাধান নির্ভুলতা তিনটি মাত্রা থেকে সমন্বিত মূল্যায়ন

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

সমাধান করুন সমরূপ ধনাত্মক-নির্দিষ্ট রৈখিক সিস্টেম Ax = b, যেখানে:

  • A হল n×n সমরূপ ধনাত্মক-নির্দিষ্ট বিরল ম্যাট্রিক্স
  • b হল ডান দিকের ভেক্টর
  • x হল সমাধানের জন্য ভেক্টর

সংযুক্ত গ্রেডিয়েন্ট (CG) পদ্ধতি ব্যবহার করে পুনরাবৃত্তিমূলক সমাধান করুন, বিভিন্ন নির্ভুলতা পাটিগণিতের কর্মক্ষমতা মূল্যায়ন করুন।

বহু-শব্দ পাটিগণিত স্থাপত্য

মৌলিক অ্যালগরিদম

ত্রুটি-মুক্ত রূপান্তর অ্যালগরিদম:

  • TwoSum(a,b): a+b কে ফ্লোটিং-পয়েন্ট ফলাফল x এবং রাউন্ডিং ত্রুটি y তে বিভক্ত করে
  • QuickTwoSum(a,b): TwoSum এর দক্ষ বৈকল্পিক, |a|≥|b| প্রয়োজন
  • TwoProdFMA(a,b): FMA অপারেশন ব্যবহার করে a×b কে ফলাফল এবং ত্রুটিতে বিভক্ত করে

দ্বিশব্দ পাটিগণিত (DW)

DWadd: [c1,c2] = DWadd(a1,a2,b1,b2)
- অপারেন্ড: 11টি FP64 অপারেশন
- স্বাভাবিকীকরণ ধাপ অন্তর্ভুক্ত (QuickTwoSum)

DWmul: [c1,c2] = DWmul(a1,a2,b1,b2)  
- অপারেন্ড: 7টি FP64 অপারেশন
- স্বাভাবিকীকরণ ধাপ অন্তর্ভুক্ত

প্রায় দ্বিশব্দ পাটিগণিত (QDW)

  • স্বাভাবিকীকরণ ধাপ বাদ দেয়, উচ্চ-নিম্ন শব্দ ওভারল্যাপ অনুমতি দেয়
  • QDWadd: 8টি অপারেশন, QDWmul: 4টি অপারেশন
  • গণনা খরচ উল্লেখযোগ্যভাবে হ্রাস

প্রায় ত্রিশব্দ পাটিগণিত (QTW)

QTWadd: [c1,c2,c3] = QTWadd(a1,a2,a3,b1,b2,b3)
- অপারেন্ড: 21টি FP64 অপারেশন
- fl(c1+c2)=c1 এবং fl(c2+c3)=c2 জোরপূর্বক করে না

QTWmul: [c1,c2,c3] = QTWmul(a1,a2,a3,b1,b2,b3)
- অপারেন্ড: 24টি FP64 অপারেশন

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. SIMD ভেক্টরকরণ অপ্টিমাইজেশন:
    • AVX2 এবং AVX-512 নির্দেশ সেট ব্যবহার করে ভেক্টরকরণ
    • QTW অ্যালগরিদম শর্তসাপেক্ষ শাখা দূর করে, ভেক্টরকরণের জন্য আরও উপযুক্ত
  2. স্বাভাবিকীকরণ কৌশল:
    • CG পদ্ধতির অবশিষ্ট ভেক্টর আপডেটের পরে স্বাভাবিকীকরণ সম্পাদন করুন
    • ত্রিশব্দ পাটিগণিতে বিট ওভারল্যাপ প্রশমিত করতে VecSum3 অ্যালগরিদম ব্যবহার করুন
  3. মিশ্র-নির্ভুলতা বাস্তবায়ন:
    • সহগ ম্যাট্রিক্স A এবং ডান দিকের ভেক্টর b FP64 এ সংরক্ষণ করুন
    • অভ্যন্তরীণ গণনা সংশ্লিষ্ট বহু-শব্দ পাটিগণিত ব্যবহার করুন

পরীক্ষামূলক সেটআপ

ডেটাসেট

SuiteSparse ম্যাট্রিক্স সংগ্রহ থেকে 8টি সমরূপ ধনাত্মক-নির্দিষ্ট ম্যাট্রিক্স ব্যবহার করুন:

ম্যাট্রিক্সমাত্রা nঅ-শূন্য উপাদান nnzপ্রয়োগ ক্ষেত্র
Hook_14981,498,02360,917,445কাঠামোগত সমস্যা
bone010986,70347,851,783মডেল হ্রাস
nd24k72,00028,715,6342D/3D সমস্যা
crankseg_263,83814,148,858কাঠামোগত সমস্যা

মূল্যায়ন সূচক

  1. সম্পাদন সময়: প্রতিটি পুনরাবৃত্তির সময় এবং মোট সংমিশ্রণ সময়
  2. পুনরাবৃত্তির সংখ্যা: সংমিশ্রণ অর্জনের জন্য প্রয়োজনীয় পুনরাবৃত্তির সংখ্যা
  3. সমাধান নির্ভুলতা: আপেক্ষিক ত্রুটি নর্ম ||xk-x*||2/||x*||2

তুলনা পদ্ধতি

  • CG-FP64: মান দ্বিগুণ-নির্ভুলতা বাস্তবায়ন
  • CG-DW: দ্বিশব্দ পাটিগণিত বাস্তবায়ন
  • CG-QDW: প্রায় দ্বিশব্দ পাটিগণিত বাস্তবায়ন
  • CG-TW: ত্রিশব্দ পাটিগণিত বাস্তবায়ন
  • CG-QTW: প্রায় ত্রিশব্দ পাটিগণিত বাস্তবায়ন

বাস্তবায়ন বিবরণ

  • হার্ডওয়্যার প্ল্যাটফর্ম: Intel Xeon Gold 6230 CPU (20 কোর, 2.10-3.90 GHz)
  • সংকলক: g++ 11.3.0, অপ্টিমাইজেশন বিকল্প -O3 -march=native
  • সমান্তরালকরণ: OpenMP + SIMD ভেক্টরকরণ
  • সংমিশ্রণ সহনশীলতা: ε = 10^-16, 10^-24, 10^-32

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

কর্মক্ষমতা ওভারহেড বিশ্লেষণ

FP64 এর তুলনায় সম্পাদন সময় ওভারহেড (100 পুনরাবৃত্তি):

  • CG-QDW: প্রায় 1.3 গুণ
  • CG-DW: প্রায় 2.1 গুণ
  • CG-QTW: প্রায় 2.4 গুণ
  • CG-TW: 67 গুণ পর্যন্ত

সংমিশ্রণ কর্মক্ষমতা তুলনা

ε=10^-16 সংমিশ্রণ সহনশীলতার অধীনে সাধারণ ফলাফল:

ম্যাট্রিক্সFP64 সময়(s)/পুনরাবৃত্তিQDW সময়(s)/পুনরাবৃত্তিQTW সময়(s)/পুনরাবৃত্তি
bone010170/21780120/12547150/11352
pdb1HYS5.4/128073.4/62854.9/5346

মূল আবিষ্কার

  1. স্বাভাবিকীকরণের প্রয়োজনীয়তা:
    • স্বাভাবিকীকরণ ছাড়া, প্রায় অ্যালগরিদম সংমিশ্রিত হতে পারে না
    • অবশিষ্ট ভেক্টর আপডেটের পরে স্বাভাবিকীকরণ সংমিশ্রণ নিশ্চিত করতে পারে
  2. QTW এর সুবিধা:
    • TW এর তুলনায় গণনা ওভারহেড উল্লেখযোগ্যভাবে হ্রাস
    • TW এর সমতুল্য নির্ভুলতা অর্জন করুন
    • SIMD ভেক্টরকরণ সমর্থন করুন, উন্নত কর্মক্ষমতা
  3. পুনরাবৃত্তির সংখ্যা হ্রাসের সুবিধা:
    • উচ্চ-নির্ভুলতা পাটিগণিত পুনরাবৃত্তির সংখ্যা হ্রাস করতে পারে
    • মোট সম্পাদন সময় FP64 বাস্তবায়নের চেয়ে কম হতে পারে

থ্রুপুট বিশ্লেষণ

SpMV অপারেশনের থ্রুপুট (GB/s):

  • FP64 এবং QDW: স্মৃতি ব্যান্ডউইথ সীমার কাছাকাছি (প্রায় 90 GB/s)
  • DW এবং QTW: SIMD অপ্টিমাইজেশনের পরে স্মৃতি-সীমিত অর্জন করুন
  • TW: শাখার প্রভাবের কারণে, কর্মক্ষমতা উল্লেখযোগ্যভাবে হ্রাস

সম্পর্কিত কাজ

বহু-শব্দ পাটিগণিত উন্নয়ন

  • মৌলিক তত্ত্ব: Dekker (1971) এর দ্বিশব্দ পাটিগণিত
  • সম্প্রসারণ পদ্ধতি: ত্রিশব্দ (TW), চতুর্শব্দ (QW) পাটিগণিত
  • সরলীকৃত বৈকল্পিক: প্রায় অ্যালগরিদম (QDW, QTW, QQW)

উচ্চ-নির্ভুলতা রৈখিক বীজগণিত লাইব্রেরি

  • QD লাইব্রেরি: দ্বিশব্দ এবং চতুর্শব্দ পাটিগণিতের Fortran/C++ বাস্তবায়ন প্রদান করে
  • XBLAS: DW পাটিগণিতের উপর ভিত্তি করে BLAS রুটিন
  • MPLAPACK: উচ্চ-নির্ভুলতা BLAS এবং LAPACK

বিরল পুনরাবৃত্তিমূলক সমাধানকারী প্রয়োগ

  • চতুর্গুণ-নির্ভুলতা CG সমাধানকারীর গবেষণা
  • মিশ্র-নির্ভুলতা পদ্ধতি
  • Ozaki স্কিমের নির্ভুল বিরল ম্যাট্রিক্স-ভেক্টর গুণন

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. প্রায় অ্যালগরিদমের সম্ভাব্যতা: উপযুক্ত স্বাভাবিকীকরণের মাধ্যমে, প্রায় অ্যালগরিদম বিরল পুনরাবৃত্তিমূলক সমাধানকারীতে কার্যকরভাবে প্রয়োগ করা যেতে পারে
  2. QTW এর সুবিধা: প্রায় ত্রিশব্দ পাটিগণিত নির্ভুলতা এবং কর্মক্ষমতার মধ্যে ভাল ভারসাম্য প্রদান করে
  3. কর্মক্ষমতা উন্নতির সম্ভাবনা: নির্দিষ্ট সমস্যায়, পুনরাবৃত্তির সংখ্যা হ্রাস অতিরিক্ত ত্বরণ প্রভাব আনতে পারে

সীমাবদ্ধতা

  1. স্বাভাবিকীকরণ ওভারহেড: নির্ভুলতা এবং সম্পাদন সময়ের মধ্যে ভারসাম্য প্রয়োজন
  2. সমস্যা-নির্ভর: কর্মক্ষমতা উন্নতির প্রভাব নির্দিষ্ট সমস্যা বৈশিষ্ট্যের উপর নির্ভর করে
  3. মূল্যায়ন পরিসীমা: শুধুমাত্র মৌলিক CG পদ্ধতি মূল্যায়ন করা হয়েছে, পূর্ব-শর্তকরণ কৌশল অন্তর্ভুক্ত নয়

ভবিষ্যত দিকনির্দেশনা

  1. স্বাভাবিকীকরণ কৌশল অপ্টিমাইজেশন: নির্ভুলতার উপর আরও ঘন ঘন স্বাভাবিকীকরণের প্রভাব গবেষণা করুন
  2. অন্যান্য পুনরাবৃত্তিমূলক পদ্ধতিতে সম্প্রসারণ: অন্যান্য সমাধানকারীতে প্রয়োগ মূল্যায়ন করুন
  3. বিতরণকৃত পরিবেশ প্রয়োগ: যোগাযোগ বিলম্ব প্রাধান্য পায় এমন পরিবেশে সম্ভাবনা
  4. নিম্ন-নির্ভুলতা ফরম্যাট বাস্তবায়ন: AI প্রসেসরে FP16/FP32 ব্যবহার করে বহু-শব্দ পাটিগণিত বাস্তবায়ন

গভীর মূল্যায়ন

শক্তি

  1. সিস্টেমেটিক গবেষণা: পুনরাবৃত্তিমূলক সমাধানকারীতে প্রায় অ্যালগরিদম কর্মক্ষমতা প্রথমবার সিস্টেমেটিকভাবে মূল্যায়ন করা
  2. উচ্চ ব্যবহারিক মূল্য: QTW অ্যালগরিদম ব্যবহারিক উচ্চ-নির্ভুলতা গণনা সমাধান প্রদান করে
  3. পর্যাপ্ত পরীক্ষা: একাধিক মাত্রা (সময়, নির্ভুলতা, সংমিশ্রণ) থেকে ব্যাপক মূল্যায়ন
  4. প্রযুক্তিগত উদ্ভাবন: SIMD অপ্টিমাইজেশন এবং স্বাভাবিকীকরণ কৌশলের যুক্তিসঙ্গত ডিজাইন

অপূর্ণতা

  1. তাত্ত্বিক বিশ্লেষণ অপর্যাপ্ত: প্রায় অ্যালগরিদম ত্রুটি সঞ্চয়ের তাত্ত্বিক বিশ্লেষণের অভাব
  2. মূল্যায়ন পরিসীমা সীমিত: শুধুমাত্র CG পদ্ধতি মূল্যায়ন করা হয়েছে, অন্যান্য পুনরাবৃত্তিমূলক পদ্ধতির যাচাইকরণের অভাব
  3. একক স্বাভাবিকীকরণ কৌশল: শুধুমাত্র একটি স্বাভাবিকীকরণ অবস্থান এবং ফ্রিকোয়েন্সি চেষ্টা করা হয়েছে

প্রভাব

  • একাডেমিক অবদান: উচ্চ-নির্ভুলতা সংখ্যাগত গণনা ক্ষেত্রে নতুন অ্যালগরিদম পছন্দ প্রদান করে
  • ব্যবহারিক মূল্য: QTW অ্যালগরিদম বাস্তব বৈজ্ঞানিক গণনা সমস্যায় সরাসরি প্রয়োগ করা যেতে পারে
  • পুনরুৎপাদনযোগ্যতা: বাস্তবায়ন বিবরণ পর্যাপ্তভাবে বর্ণিত, পুনরুৎপাদন সহজ করে

প্রযোজ্য পরিস্থিতি

  1. বৈজ্ঞানিক গণনা: উচ্চ-নির্ভুলতা সমাধানের প্রয়োজন এমন বড় বিরল রৈখিক সিস্টেম
  2. প্রকৌশল সিমুলেশন: কাঠামোগত বিশ্লেষণ, বৈদ্যুতিক চৌম্বক ক্ষেত্র গণনা এবং অন্যান্য প্রয়োগ
  3. সম্পদ-সীমিত পরিবেশ: হার্ডওয়্যার চতুর্গুণ-নির্ভুলতা সমর্থন অভাব সিস্টেম

সংদর্ভ

এই গবেষণাপত্র 29টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যা বহু-শব্দ পাটিগণিত তত্ত্ব, উচ্চ-নির্ভুলতা রৈখিক বীজগণিত লাইব্রেরি, বিরল পুনরাবৃত্তিমূলক সমাধানকারী এবং অন্যান্য মূল ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।