Parallel Reduction
প্যারালাল রিডাকশন
একটা associative operator (যেমন sum, max) দিয়ে n-টা element-কে tree-আকারে সাজিয়ে একত্রিত করা — মোট কাজ সিরিয়ালের সমান (n−1), কিন্তু গভীরতা log n। Prefix sum (scan)-এর সমান্তরাল সংস্করণে (Hillis-Steele) উল্টো trade-off — গভীরতা log n কিন্তু মোট কাজ n log n।
also: map-reduce-scan, prefix sum, scan
n-টা সংখ্যার sum সিরিয়ালি করলে n-1টা +, সিরিয়ালি একের
পর এক — depth n-1। কিন্তু + associative বলে জোড়ায় জোড়ায়
আগে যোগ করে একটা tree বানানো যায়:
3 1 4 1 5 9 2 6
\/ \/ \/ \/
4 5 14 8 ← ৪টা যোগ, একসাথে
\ / \ /
9 22 ← ২টা যোগ, একসাথে
\ /
31 ← ১টা যোগমোট কাজ (work) অপরিবর্তিত — n-1 = 7টা যোগই। যা কমেছে সেটা
depth — log₂ n = 3 ধাপ, n-1 = 7 নয়। যথেষ্ট প্রসেসর
থাকলে (GPU-র হাজার হাজার [[simd]]-lane), সময় n-এর বদলে
log n-এর সমানুপাতিক — এটাই [[asymptotic-notation]] লেসনের
recursion-tree-গভীরতা-বনাম-চেইন-দৈর্ঘ্য যুক্তির সরাসরি প্রয়োগ।
Scan (prefix sum) প্রথম দেখায় সিরিয়াল মনে হয় — output[i]
তো output[i-1]-এর উপর নির্ভর করে বলে মনে হচ্ছে
([1,2,3,4] → [1,3,6,10])। কিন্তু Hillis-Steele algorithm
offset = 1, 2, 4, ... দ্বিগুণ করতে করতে log n ধাপে সঠিক
scan করে ফেলে। মূল্য — মোট কাজ বেড়ে যায়, n log n - (n-1)-এ,
সিরিয়ালের n-1-এর চেয়ে বেশি (n=1024-এ প্রায় ৯ গুণ বেশি
কাজ)। এটাই reduce-এর থেকে মৌলিক পার্থক্য: reduce-এ tree
পুনর্গঠন বিনামূল্যে depth কমায়, scan-এর সরল সমান্তরাল
সমাধানে depth কমাতে বাড়তি কাজ দিতে হয়। Work-efficient
বিকল্প (Blelloch scan, Θ(n) work) জটিলতর, দুই-ধাপের (up-sweep/
down-sweep) algorithm।
reduce/scan-এর operator অবশ্যই associative হতে হবে —
floating-point addition কঠোরভাবে associative নয় (rounding),
তাই একটা GPU tree-reduce sum আর CPU সিরিয়াল sum সামান্য ভিন্ন
ফলাফল দিতে পারে; আর map (Level ১১-এর SIMD/CUDA vector-add)
এই pattern-দ্বয়ের তৃতীয় সঙ্গী — Hadoop/Spark-এর MapReduce
হুবহু এই একই তিনটা pattern, শুধু single-GPU স্কেল থেকে
data-center স্কেলে।