محاسبات تصادفی

محاسبات تصادفی مجموعه ای از تکنیک هاست که مقادیر پیوسته را توسط جریان بیت های تصادفی نشان می دهد. سپس محاسبات پیچیده را می توان با عملیات بیتی ساده در جریان ها محاسبه کرد. البته باید توجه داشت که محاسبات تصادفی از مطالعه الگوریتم های تصادفی متمایز است.

انگیزه و یک مثال ساده

فرض کنید که ${\displaystyle p,q\in [0,1]}$ داده می شود، و ما می خواهیم ${\displaystyle p\times q}$ محاسبه کنیم . محاسبات تصادفی این عملیات را با استفاده از احتمال به جای محاسبات انجام می‌دهد.

به طور خاص، فرض کنید که دو جریان بیت تصادفی و مستقل به نام اعداد تصادفی (یعنی فرآیندهای برنولی) وجود دارد، که در آن احتمال در جریان اول برابر است با $p$ و احتمال در جریان دوم ${\displaystyle q}$ است. ما می توانیم AND منطقی دو جریان را در نظر بگیریم.

...	1	0	1	1	0	1	${\displaystyle a_{i}}$
...	0	1	1	0	1	1	${\textstyle {\displaystyle b_{i}}}$
...	0	0	1	0	0	1	${\displaystyle a_{i}\land b_{i}}$

احتمال رخداد عدد 1 در جریان خروجی برابر با ${\displaystyle p\times q}$ است. با مشاهده تعداد کافی بیت خروجی و اندازه گیری فراوانی عدد 1، می توان ${\displaystyle p\times q}$ را با دقت دلخواه تخمین زد.

عملیات فوق یک محاسبه نسبتاً پیچیده (${\displaystyle p\times q}$) را به یک سری عملیات بسیار ساده (ارزیابی ${\displaystyle a_{i}\land b_{i}}$) بر روی بیت های تصادفی تبدیل می کند. از دیدگاه دیگر، با فرض جدول درستی یک دروازه AND، تفسیر متداول این است که خروجی تنها در صورتی درست است که ورودی های A و B درست باشند. با این حال، اگر جدول را به صورت عمودی تفسیر کنیم، (0011) AND (0101) برابر با (0001) است، یعنی 1/2 × 1/2 = 1/4، که دقیقاً یک ضرب حسابی است. از آنجایی که اطلاعات به صورت توزیع احتمال ارائه می شود، ضرب احتمال به معنای واقعی کلمه یک عمل AND است.

OUT	B	A
0	0	0
0	1	0
0	0	1
1	1	1

تاریخچه

محاسبات تصادفی برای اولین بار در سال 1953 توسط جان فون نویمان در یک مقاله پیشگامانه معرفی شد. با این حال، این نظریه تا پیشرفت‌های محاسباتی دهه 1960 نتوانست به طور کامل توسعه یابد، که عمدتاً از طریق مجموعه‌ای از تلاش‌های همزمان و موازی در ایالات متحده و بریتانیا انجام شد. تا اواخر دهه 1960، توجه به طراحی سخت‌افزارهای ویژه برای انجام محاسبات تصادفی معطوف شد. بسیاری از این ماشین‌ها بین سال‌های 1969 و 1974 ساخته شدند؛ RASCEL در این مقاله به تصویر کشیده شده است.

علیرغم علاقه شدید در دهه‌های 1960 و 1970، محاسبات تصادفی در نهایت نتوانست با منطق دیجیتال سنتی رقابت کند، به دلایلی که در زیر توضیح داده شده است. اولین (و آخرین) سمپوزیوم بین‌المللی محاسبات تصادفی در سال 1978 برگزار شد؛ تحقیقات فعال در این زمینه در چند سال آینده کاهش یافت.

اگرچه محاسبات تصادفی به عنوان یک روش کلی محاسبات کاهش یافت، اما در چندین کاربرد نویدبخش بوده است. تحقیقات سنتی بر روی برخی از وظایف در یادگیری ماشین و کنترل متمرکز شده است. اخیراً، علاقه به رمزگشایی تصادفی معطوف شده است که محاسبات تصادفی را برای رمزگشایی کدهای تصحیح خطا اعمال می‌کند. اخیراً، مدارهای تصادفی با موفقیت در وظایف پردازش تصویر مانند تشخیص لبه و آستانه‌گذاری تصویر استفاده شده‌اند. پیشرفت اخیر در مدارهای تصادفی همچنین مزایای سرعت و کارایی انرژی امیدوارکننده‌ای را در شتاب‌دهنده‌های سخت‌افزاری هوش مصنوعی (AI) در محاسبات لبه نشان می‌دهد.

نقاط قوت و ضعف

اگرچه محاسبات تصادفی در گذشته شکست خورده است، اما ممکن است همچنان برای حل برخی مشکلات مرتبط باشد. برای درک اینکه چه زمانی مرتبط است، مقایسه محاسبات تصادفی با روش‌های سنتی‌تر محاسبات دیجیتال مفید است.

نقاط قوت

فرض کنید می‌خواهیم دو عدد را هر کدام با دقت n بیت ضرب کنیم. با استفاده از روش ضرب طولانی معمولی، باید n^2 عملیات انجام دهیم. با محاسبات تصادفی، می‌توانیم هر تعداد بیت را با هم AND کنیم و مقدار مورد انتظار همیشه صحیح خواهد بود. (با این حال، با تعداد کمی نمونه، واریانس نتیجه واقعی را بسیار نادرست می‌کند).

علاوه بر این، عملیات‌های زیربنایی در یک ضرب‌کننده دیجیتال جمع‌کننده‌های کامل هستند، در حالی که یک کامپیوتر تصادفی فقط به یک دروازه AND نیاز دارد. علاوه بر این، یک ضرب‌کننده دیجیتال به طور ساده به 2n سیم ورودی نیاز دارد، در حالی که یک ضرب‌کننده تصادفی فقط به دو سیم ورودی نیاز دارد. (اگر ضرب‌کننده دیجیتال خروجی خود را سریال کند، در این صورت نیز فقط به دو سیم ورودی نیاز دارد.)

علاوه بر این، محاسبات تصادفی در برابر نویز مقاوم است؛ اگر چند بیت در یک جریان تغییر کنند، این خطاها تأثیر قابل توجهی بر راه حل نخواهند داشت.

علاوه بر این، عناصر محاسبات تصادفی می‌توانند تاخیر در زمان ورود ورودی‌ها را تحمل کنند. مدارها حتی زمانی که ورودی‌ها از نظر زمانی نامرتب باشند، به درستی کار می‌کنند. در نتیجه، سیستم‌های تصادفی می‌توانند برای کار با ساعت‌های محلی ارزان‌قیمت تولید شده به جای استفاده از یک ساعت جهانی و یک شبکه توزیع ساعت گران‌قیمت طراحی شوند.

در نهایت، محاسبات تصادفی برآوردی از راه‌حل ارائه می‌دهد که با افزایش جریان بیت دقیق‌تر می‌شود. به طور خاص، تخمین تقریبی را بسیار سریع ارائه می‌دهد. این ویژگی معمولاً به عنوان دقت تدریجی شناخته می‌شود، که نشان می‌دهد دقت اعداد تصادفی (جریان‌های بیت) با پیشرفت محاسبات افزایش می‌یابد. این مانند این است که مهم‌ترین بیت‌های عدد قبل از کم‌اهمیت‌ترین بیت‌های آن می‌رسند؛ برخلاف مدارهای حسابی متداول که مهم‌ترین بیت‌ها معمولاً آخرین بار می‌رسند. در برخی از سیستم‌های تکراری، راه‌حل‌های جزئی به دست آمده از طریق دقت تدریجی می‌توانند بازخورد سریع‌تری نسبت به روش‌های محاسبات سنتی ارائه دهند و منجر به همگرایی سریع‌تر شوند.

نقاط ضعف

محاسبات تصادفی ذاتاً تصادفی است. وقتی یک جریان بیت تصادفی را بررسی می‌کنیم و سعی می‌کنیم مقدار زیربنایی را بازسازی کنیم، دقت موثر را می‌توان با واریانس نمونه اندازه‌گیری کرد. در مثال بالا، ضرب‌کننده دیجیتال عددی را با دقت ${\displaystyle 2n}$ بیت محاسبه می‌کند، بنابراین دقت ${\displaystyle 2^{-2n}}$ است. اگر از یک جریان بیت تصادفی برای تخمین یک عدد استفاده می‌کنیم و می‌خواهیم انحراف استاندارد تخمین ما از راه‌حل حداقل ${\displaystyle 2^{-2n}}$ باشد، به ${\displaystyle O(2^{4n})}$ نمونه نیاز خواهیم داشت. این نشان دهنده افزایش نمایی در کار است. با این حال، در برخی از کاربردها، می‌توان از ویژگی دقت تدریجی محاسبات تصادفی برای جبران این کاهش نمایی استفاده کرد.

نقطه ضعف دوم این است که ، محاسبات تصادفی به روشی برای تولید جریان‌های بیت تصادفی بایاس نیاز دارد. در عمل، این جریان‌ها با استفاده از ژنراتورهای اعداد شبه تصادفی تولید می‌شوند. متأسفانه، تولید بیت‌های (شبه-)تصادفی نسبتاً پرهزینه است (در مقایسه با هزینه، مثلاً یک جمع‌کننده کامل). بنابراین، مزیت سطح گیت محاسبات تصادفی معمولاً از بین می‌رود.

سوم: تحلیل محاسبات تصادفی فرض می‌کند که جریان‌های بیت مستقل (بدون همبستگی) هستند. اگر این فرض برقرار نباشد، محاسبات تصادفی می‌تواند به شدت شکست بخورد. برای مثال، اگر سعی کنیم ${\displaystyle p^{2}}$را با ضرب یک جریان بیت برای $p$ در خودش محاسبه کنیم، این فرآیند شکست می‌خورد: از آنجایی که${\displaystyle a_{i}\land a_{i}=a_{i}}$، محاسبات تصادفی ${\displaystyle p\times p=p}$ را به دست می‌دهد که به طور کلی درست نیست (مگر اینکه $p$=0 یا 1 باشد). در سیستم‌هایی با بازخورد، مشکل همبستگی می‌تواند به روش‌های پیچیده‌تری بروز کند. سیستم‌های پردازنده‌های تصادفی مستعد قفل شدن هستند، جایی که بازخورد بین اجزای مختلف می‌تواند به حالت قفل شده دست یابد. برای تلاش برای اصلاح قفل شدن، باید تلاش زیادی برای از همبستگی خارج کردن سیستم صرف شود.

چهارم: اگرچه برخی از توابع دیجیتال دارای همتایان تصادفی بسیار ساده‌ای هستند (مانند ترجمه بین ضرب و دروازه AND)، بسیاری از آنها اینطور نیستند. تلاش برای بیان این توابع به صورت تصادفی می‌تواند باعث ایجاد آسیب‌شناسی‌های مختلف شود. برای مثال، رمزگشایی تصادفی نیاز به محاسبه تابع ${\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}$دارد. هیچ عمل بیت واحدی وجود ندارد که بتواند این تابع را محاسبه کند؛ راه حل معمول شامل تولید بیت‌های خروجی همبسته است که همانطور که در بالا دیدیم، می‌تواند باعث ایجاد مشکلات زیادی شود.

در توابع دیگر (مانند عملگر میانگین‌گیری${\displaystyle f(p,q)\rightarrow (p+q)/2}$ که نیاز به کاهش یا افزایش نمونه‌برداری جریان دارند. تعادل بین دقت و حافظه می‌تواند چالش‌برانگیز باشد.

رمزگشایی تصادفی

اگرچه محاسبات تصادفی به عنوان یک روش محاسبات عمومی دارای برخی محدودیت‌ها است، اما در برخی کاربردها نقاط قوت خود را نشان می‌دهد. یکی از موارد قابل توجه، رمزگشایی برخی کدهای تصحیح خطا است.

در توسعه‌های مرتبط با محاسبات تصادفی، روش‌های بسیار کارآمدی برای رمزگشایی کدهای LDPC با استفاده از الگوریتم انتشار باور توسعه یافتند. انتشار باور در این زمینه شامل تخمین مجدد تکراری برخی پارامترها با استفاده از دو عملیات اساسی است (در اصل، یک عملیات XOR احتمالی و یک عملیات میانگین‌گیری).

در سال 2003، محققان متوجه شدند که این دو عملیات را می‌توان به سادگی با محاسبات تصادفی مدل‌سازی کرد. علاوه بر این، از آنجایی که الگوریتم انتشار باور تکراری است، محاسبات تصادفی راه‌حل‌های جزئی ارائه می‌دهد که می‌تواند به همگرایی سریع‌تر منجر شود. پیاده‌سازی‌های سخت‌افزاری رمزگشاهای تصادفی بر روی FPGAها ساخته شده‌اند. طرفداران این روش‌ها استدلال می‌کنند که عملکرد رمزگشایی تصادفی با جایگزین‌های دیجیتال رقابت می‌کند.

روش‌های قطعی برای محاسبات تصادفی

روش‌های قطعی SC برای انجام محاسبات کاملاً دقیق با مدارهای SC توسعه یافته‌اند. اصل اساسی این روش‌ها این است که هر بیت از یک جریان بیت دقیقاً یک بار با هر بیت از جریان بیت‌های دیگر تعامل می‌کند. برای تولید نتیجه کاملاً دقیق با این روش‌ها، عملیات باید برای حاصلضرب طول جریان‌های بیت ورودی اجرا شود. روش‌های قطعی بر اساس جریان‌های بیت یکتایی، جریان‌های بیت شبه‌تصادفی و جریان‌های بیت کم‌اختلاف توسعه یافته‌اند.

انواع محاسبات تصادفی

چندین نوع مختلف از الگوی اساسی محاسبات تصادفی وجود دارد. اطلاعات بیشتر را می توان در کتاب ارجاع شده توسط مارس و پوپل باوم یافت.

پردازش بسته‌ای شامل ارسال تعداد ثابتی بیت به جای یک جریان است. یکی از مزایای این رویکرد بهبود دقت است. برای درک دلیل، فرض کنید s بیت ارسال می‌کنیم. در محاسبات تصادفی معمولی، به دلیل واریانس تخمین، می‌توانیم دقت تقریباً ${\displaystyle O(1/{\sqrt {s}})}$مقدار مختلف را نشان دهیم. در پردازش بسته‌ای، می‌توانیم دقت${\displaystyle 1/s}$را نشان دهیم. با این حال، پردازش بسته‌ای همان پایداری خطای پردازش تصادفی معمولی را حفظ می‌کند.

پردازش ارگودیک شامل ارسال جریانی از بسته‌ها است که مزایای پردازش تصادفی و بسته‌ای معمولی را به همراه دارد.

پردازش انفجاری یک عدد را با یک جریان پایه بالاتر کدگذاری می‌کند. به عنوان مثال، عدد 4.3 را با ده رقم اعشار به صورت زیر کدگذاری می‌کنیم: 4444444555 زیرا میانگین مقدار جریان قبلی 4.3 است. این نمایش مزایای مختلفی دارد: هیچ تصادفی‌سازی وجود ندارد زیرا اعداد به ترتیب صعودی ظاهر می‌شوند، بنابراین مسائل PRNG از بین می‌روند، اما بسیاری از مزایای محاسبات تصادفی حفظ می‌شوند (مانند تخمین‌های جزئی از راه‌حل). علاوه بر این، دقت خطی پردازش بسته‌ای و ارگودیک را حفظ می‌کند.