ধার করা ভরা ডিস্ক কম্পিউটারকে দ্রুততর করে
কিছু সমস্যা সময়ের দিক থেকে সস্তা কিন্তু মেমরির জন্য লোভী, কিছু ঠিক উল্টো। কয়েকটি মৌলিক কাজের জন্য তাত্ত্বিকেরা এই আদান-প্রদানের কঠোর সীমা প্রমাণ করেছেন: ছোট কার্যকরী মেমরি নিয়ে আপনি দ্রুত হতে পারবেন না। একটি নতুন গবেষণাপত্র দেখাচ্ছে, এক অদ্ভুত সম্পদ, অর্থাৎ এমন মেমরি যা আগে থেকেই ভরা এবং অক্ষত অবস্থায় ফেরত দিতে হবে, এই সীমাগুলো ভেঙে দেয়।
ধার করা হার্ড ড্রাইভ
এই মডেলের নাম ক্যাটালিটিক কম্পিউটিং, যা 2014 সালে Buhrman, Cleve, Koucký, Loff ও Speelman প্রবর্তন করেন। একটি অ্যালগরিদম পায় একটি ছোট্ট পরিষ্কার মেমরি, n আকারের ইনপুটের জন্য মোটামুটি log n বিট, আর সঙ্গে একটি বিশাল নোংরা মেমরি, যা আগে থেকেই এমন যথেচ্ছ ডেটায় ভরা যা সে বেছে নেয়নি। সে দুটোই যেমন খুশি ব্যবহার করতে পারে, কিন্তু থামার সময় নোংরা মেমরির প্রতিটি বিট ঠিক আগের মতোই থাকতে হবে।
লেখকেরা প্রচলিত উপমাটি ব্যবহার করেন: একটি হিসাব চালাতে আপনি বন্ধুর বিশাল হার্ড ড্রাইভ ধার নিলেন, মূল্যবান ডিজিটাল স্মৃতিতে ভরা। আপনি বন্ধু হারাতে চান না, তাই কাজ শেষে প্রতিটি বিট আগের অবস্থায় ফিরিয়ে দেন।
মডেলটি প্রথমে তৈরি হয়েছিল এটা প্রমাণ করতে যে এমন মেমরি অকেজো। স্বাভাবিক বুদ্ধিতে, সবকিছু ফিরিয়ে দিতে হলে সব তথ্য রেখে দিতে হয়, ফলে কখনো কোনো জায়গা খালি হয় না। আশ্চর্যজনকভাবে, উল্টোটাই সত্যি প্রমাণিত হলো: ভরা মেমরি দিয়ে এমন সমস্যার সমাধান করা যায়, যা কেবল পরিষ্কার মেমরি দিয়ে কেউ সমাধান করতে জানে না। কিন্তু সেই ফলাফলগুলো ছিল জায়গা (স্পেস) নিয়ে, আর অ্যালগরিদমগুলো ছিল অত্যন্ত ধীর।
প্রমাণিত সম্ভাব্যতার চেয়েও দ্রুত
Adelmo Morrison Orozco, Nathan Sheffield ও Ryan Williams (MIT) এবার নজর দিয়েছেন গতির দিকে। লগারিদমিক পরিষ্কার মেমরি আর বহুপদী পরিমাণ ধার করা মেমরি নিয়ে তাঁরা এমন অ্যালগরিদম দিয়েছেন যা:
- একটি তালিকা সাজায় এবং বিচ্ছিন্ন ফুরিয়ে রূপান্তর গণনা করে n^(1+o(1)) সময়ে, অর্থাৎ প্রায় রৈখিক সময়ে;
- ম্যাট্রিক্স গুণ করে n^(ω+o(1)) সময়ে, সীমাহীন মেমরি থাকলে সবচেয়ে ভালো জানা পদ্ধতির মতোই দ্রুত।
ধার করা ডিস্ক ছাড়া এটা প্রমাণিত যে সময় ও মেমরির গুণফল সাজানো ও ফুরিয়ে রূপান্তরের জন্য অন্তত n² মাত্রার এবং ম্যাট্রিক্স গুণের জন্য n³ মাত্রার হতে হবে। তাই এই ক্যাটালিটিক অ্যালগরিদমগুলো এমন গতিতে পৌঁছায়, যেখানে কোনো সাধারণ ছোট-মেমরির অ্যালগরিদম পৌঁছাতে পারে না। লেখকেরা একে বলছেন প্রথম শর্তহীন প্রমাণ যে ক্যাটালিটিক অ্যালগরিদম তাদের নন-ক্যাটালিটিক প্রতিরূপদের ছাড়িয়ে যায়।
বদলাও, পড়ো, ফিরিয়ে দাও
মূল উপাদান একটি ছোট সমাবেশমূলক (কম্বিনেটোরিয়াল) কৌশল। ধরুন একটি অ্যালগরিদম ধার করা মেমরির একটি অংশকে একটি অজানা মান τ এবং τ + x-এর মধ্যে বদলাতে পারে, যেখানে x হলো সেই ফলাফল যা তার দরকার। একটি বড় “সহায়ক” টেবিলে, সেটিও ধার করা, সযত্নে বাছাই করা কিছু ঘরে 1 যোগ করুন। τ অবস্থানের ঘরটি এক বাড়ে যদি এবং কেবল যদি x একটি নির্দিষ্ট সেটের সদস্য হয়। তারপর প্রতিটি ধাপ উল্টো দিকে চালান, আর ডিস্কটি আগের মতো হয়ে যায়, কেবল আপনার চাওয়া উত্তরের বিটটুকু ছাড়া।
এই কৌশল স্তরে স্তরে সাজিয়ে অগভীর সার্কিট দ্রুত মূল্যায়ন করা যায়। এরপর লেখকেরা সর্টিং নেটওয়ার্ক, দ্রুত ফুরিয়ে রূপান্তর এবং দ্রুত ম্যাট্রিক্স গুণকে এমন সার্কিট হিসেবে নতুন করে লেখেন। পাটিগণিতে কেবল সেই স্তরগুলোর বাড়তি খরচ লাগে, যেগুলো দুটি অজানাকে গুণ করে; বিশুদ্ধ রৈখিক স্তরগুলো প্রায় বিনামূল্যে মেলে।
একটি ন্যায্য তুলনা
একটি আপত্তি: প্রচলিত সীমাগুলো ধরে নেয় যে উত্তর একবারই লেখা হয়, বাঁ থেকে ডানে, একটি আলাদা আউটপুট টেপে, অথচ ক্যাটালিটিক অ্যালগরিদম তাদের উত্তর লেখে ধার করা ডিস্কে। গবেষণাপত্রটি এর জবাব দেয়। লেখকেরা দেখান যে তাঁদের অ্যালগরিদম একটি আউটপুট টেপের ওপর দুবার পার হয়ে উত্তর লিখতে পারে, এবং সাধারণ অ্যালগরিদমের জন্য দুবার পার হওয়া একবারের চেয়ে বেশি সাহায্য করে না। তাই সীমাগুলো তখনও খাটে, এবং পার্থক্যটি টিকে থাকে। তাঁরা এটাও প্রমাণ করেন যে ধার করা ডিস্ক থাকলেও একবার পার হওয়া যথেষ্ট নয়: তখন সাজানো সেই একই n² দেয়ালে ধাক্কা খায়।
উপকারভোগীদের দীর্ঘ তালিকা
একই সরঞ্জাম দ্রুত ক্যাটালিটিক অ্যালগরিদম দেয় বড় পূর্ণসংখ্যা ও বহুপদী গুণ, নেটওয়ার্কে ত্রিভুজ গোনা ও ক্লিক (clique) খোঁজা, পথ ও চক্র শনাক্ত করা, এবং ওয়াইল্ডকার্ডসহ টেক্সট প্যাটার্ন মেলানোর জন্য। তাদের চলার সময় ছোটখাটো গুণক বাদে সেই সেরা জানা অ্যালগরিদমগুলোর সমান, যাদের হাতে যত খুশি মেমরি আছে। প্রতিটি ক্ষেত্রে ধার করা মেমরিকে ঠিক যেমন ধার দেওয়া হয়েছিল তেমনই ফেরত আসতে হয়।