دانلود فایل شرح زبان سی شارپ و قابلیت های تحت وب آن (دات نت)
| دسته بندی | برنامه نویسی |
| بازدید ها | 11 |
| فرمت فایل | doc |
| حجم فایل | 146 کیلو بایت |
| تعداد صفحات فایل | 95 |
شرح زبان سی شارپ و قابلیت های تحت وب آن (دات نت)
مقدمه
C# یکی از زبانهای جدید برنامه‌سازی شی‌گرا است که با ارائة رهیافت Component-Based به طراحی و توسعه نرم‌افزار می‌پردازد. آنچه ما در حال حاضر از زبانهای برنامه‌سازی Component-Based در اختیار داریم و آنچه که C# در اختیار ما قرار میدهد، افق جدیدی به سوی تولید و طراحی نرمافزارهای پیشرفته را در روی ما قرار می‌دهند.
نرم‌افزار، به عنوان یک سرویس، هدف اصلی نسل بعدی در سیستمهای محاسباتی است. برای مثال، C# زبانی مناسب برای تولید و طراحی صفحات وب، ایجاد اجزایی با قابلیت استفاده مجدد و ایجاد محیط‌هایی چند رسانه‌ای را به عنوان زبانی که هدفش توسعه ایجاد نرمافزارهای پیشرفته است، در اختیار ما قرار میدهد.
زبان برنامه‌سازی C#، به همراه تکنولوژی جدید شرکت نرم‌افزاری مایکروسافت یعنیNET. ارائه گردید، از این رو از تکنولوژیNET. این شرکت بهره می‌برد. پس در ابتدا به بیان مطالبی درباره محیطNET. می‌پردازیم.
فصل اول:تکنولوژیNET.
چراNET.؟
در گذشته زبانهای برنامه‌سازی، سیستمهای عامل و محیط‌های اجرایی نرمافزارها برای دوره‌ای خاص ساخته می‌شدند. هنگامیکه برنامه‌ها از محیط‌های رومیزی(Desktop) به اینترنت منتقل می‌شدند، ابزارهای موجود نیازمند API هایی اضافی و قابلیتهای دیگری بودند. بیشتر این قابلیتها در کنار زبانهای برنامه‌سازی بعنوان ابزارهایی جهت رفع این نیازمندیها ارائه می‌شدند. هرچند این ابزارهای اضافی بصورت قابل توجهی نیازمندیها را حل کرده و باعث رسیدن اینترنت به وضعیت کنونی شدند، اما همچنان مسائل بسیاری وجود داشت که نیاز به حل شدن داشتند.
NET. به منظور پشتیبانی از کاربردهای عصر جدید اینترنت ساخته شد. مواردی همچون گسترش، امنیت و versioning، که از مسایل مهممی بودند، توسط NET. پوشش داده شدند. قسمت مرکزیNET. بخش CLR (Common Language Runtime) است که یک موتور اجرایی مجازی است که از توسعه، امنیت و ارتقای نسخه کد پشتیبانی می‌نماید. در گذشته چنین امکاناتی برای کدهای کامپایل شده فراهم نبود. بدلیل اینکهNET. توانست بر این مشکلات اساسی فائق آید، راه حل قدرتمندتری جهت ساخت برنامه‌های تحت اینترنت به شمار می‌رود.
NET. چیست؟
NET. محیطی جهت ساخت برنامه‌های توزیع شده است که شامل ابزارهایی نظیر ""کتابخانه کلاسهای پایه"(BCL: Base Class Library)، CLR و زبانهای برنامه‌نویسی است. این ابزارها امکان ساخت انواع مختلفی از نرمافزارها، از قبیل فرمهای ویندوز، ADONET.، ASPNET. و سرویسهای وب، را فراهم می‌آورند.
فرمهای ویندوز، مجموعه‌ای از کتابخانه‌ها جهت ساخت رابطهای کاربر گرافیکی برای برنامه‌های کاربردی است. این کتابخانه‌ها اغلب API های Win32 را در خود دارا می‌باشند. همچنین امکان استفاده از رهیافت شی‌گرایی را جهت تولید آسان برنامه‌های تحت ویندوز، فراهم می‌آورند.
ADONET. مجموعه‌ای از کلاسهای شی‌گرایی است که جهت ساخت مولفه‌های داده و سطوح دسترسی داده در برنامه‌های n-tiered مورد استفاده قرار می‌گیرد.
ASPNET. شامل مدل برنامه‌نویسی فرمهای وب است که بوسیلة آن برنامه‌های تحت وب ساخته شده و تحت اینترنت قابلیت اجرا پیدا کرده و از طریق مرورگر(Browser) قابل دسترسی می‌باشند. این روش مدل بهبود یافته برنامه‌سازی وب است که در آن کدها در سرور کامپایل میشوند ولی همانند صفحات HTML در کامپیوتر مشتری اجرا میشوند.
سرویسهای وب، رهیافتی جدید، مستقل از platform و استاندارد، جهت ایجاد ارتباط و فعالیت بین سیستمهای ناهمگون در اینترنت، می‌باشند. سرویسهای وبNET.، از زیر ساخت شی‌گرایی برنامه‌نویسی ASPNET. استفاده می‌کنند، اما همچنان از استانداردهای باز و مدلی بر پایة پیغام(Message Based Model) استفاده می‌نمایند. استفاده از استانداردهای باز از قبیل XML، WSDL و UDDI باعث میشوند تا سرویسهای وب با سایر سرویسهای وب استاندارد که پیاده‌سازی‌هایی متفاوت دارند، بدون توجه به محیط و platform آنها، ارتباط برقرار نمایند.
این چند نمونه، اندکی از انواع مختلف نرم‌افزارهایی بودند که می‌توان تحتNET. به پیاده‌سازی آنها پرداخت.
کتابخانه‌های کلاسهای پایه(Base Class Library: BCL)
BCL درNET.، شامل هزاران نوع قابل استفاده، جهت افزایش بهره‌وری در ساخت برنامه‌هایNET. است. به علت گستردگی BCL یادگیری تمام کلاسهای آن وقت‌گیر بوده و امکان پذیر نمی‌باشد، به همین دلیل برای صرفه‌جویی در زمان بهتر است قبل از ایجاد یک نوع خاص به جستجوی نوعهای موجود در BCL بپردازیم. نگاهی کلی به BCL می‌تواند بسیار سودمند باشد. جدول زیر Namespace های مهم و توضیح نوعهای مختلف BCL را نمایش میدهد.
|
NET. Namespaces |
|
|
Namespace |
Description |
|
System |
The most commonly used types. |
|
System.CodeDom |
Allows creating types that automate working with source code, that is, compilers and code creation tools. |
|
System.Collections |
Collection types such as ArrayList, Hashtable, and Stack. |
|
System.ComponentModel |
Supports building reusable components. |
|
System.Configuration |
Types for working with various kinds of XML configuration files. |
|
System.Data |
Most of the types for ADONET. database programming. Other types are in namespaces that are specific to a database or data interface. |
|
System.Diagnostics |
Process, EventLog, and Performance Counter types. |
|
System.DirectoryServices |
Managed interface for accessing Windows Active Directory Services. |
|
System.Drawing |
GDI+ types. |
|
System.EnterpriseServices |
COM+ types. |
|
System.Globalization |
Types for culture-specific support of calendars, formatting, and languages. |
|
System.IO |
Directory, File, and Stream types. |
|
System.Management |
APIs for performing WMI tasks. |
|
System.Messaging |
Types for working with message queues. |
|
SystemNET. |
Access to networking protocol types. |
|
System.Reflection |
Reflection APIs for inspecting assembly metadata. |
|
System.Resources |
Types for culture-specific resource management. |
|
System.Runtime |
COM Interop, Remoting, and Serialization support. |
|
System.Security |
Code access security, role-based security, and cryptography types. |
|
System.ServiceProcess |
Types for building Windows Services. |
|
System.Text |
Text encoding/decoding, byte array from/to string translation, the StringBuilder class, and regular expressions. |
|
System.Timers |
Timer types. |
|
System.Threading |
Threads and synchronization types. |
|
System.Web |
HTTP Communications, ASPNET., and Web Services types. |
|
System.Windows |
Windows Forms types. |
|
System.XML |
All XML support types, including XML Schema, XmlTextReaders/XmlTextWriters, XPath, XML Serialization, and XSLT. |
جدول 1-1 Namespaceهای مهم و رایج
هر Namespace مجموعه‌ای از کلاسهای از پیس ساخته شدةNET. است که می‌توان از آنها در برنامه‌های مختلف استفاده نمود.
(Common Language Runtime)CLR
CLR یک موتور اجرایی است که با هدف اصلی اجرای هدایت شدة کدها درNET. ایجاد گردیده است. CLR به مدیریت اجرا، ارتقای نسخه و امنیت تمامی کدها درNET. می‌پردازد. به همین دلیل کدهایNET. یا C# اغلب تحت عنوان کدهای مدیریت شده، شناخته میشوند.(Managed Code) تمامی کدهایی که به CLR مرتبت هستند، تحت عنوان "مدیریت شده" و کدهایی توسط CLR مدیریت نشده‌اند، بلکه مستقیماً به کد ماشین تبدیل میشوند، تحت عنوان "مدیریت نشده" بیان میشوند.
کدهای مدیریت شده، به کد ماشین کامپایل نمی‌شوند، بلکه به زبان سطح میانی مایکروسافت(MSIL) کامپایل شده و مورد استفاده قرار می‌گیرند. این زبان سطح میانی را می‌توان زبانی شبیه به زبان اسمبلی تصور کرد. IL در حافظه بارگذاری می‌شود و بلافاصله بوسیلة CLR در حافظه به کد ماشین کامپایل می‌گردد.
برنامه‌هایNET. از اسمبلی‌هایی تشکیل شدهاند که اجزای خودکار منطقی توسعه، شناسایی و امنیت به حساب می‌آیند و تفاوت آنها با روشهای قدیمی در آن است که اسمبلی می‌تواند شامل یک یا چندین فایل باشد. اسمبلیNET. به صورت یک فایل اجرایی تک یا یک فایل کتابخانه‌ای است، اما ممکن است حاوی ماژول‌ها، که کدهایی غیر اجرایی بوده و قابلیت استفادة مجدد را دارند، نیز باشد.
مسئلة مهم دیگر در مورد CLR، نحوة بارگذاری(Load) و اجرای برنامه توسط آن است. به محض اینکه برنامةNET. شروع به اجرا می‌کند، ویندوز اسمبلیNET. راتشخیص داده و CLR را اجرا می‌کند. سپس CLR نقطه شروع برنامه را شناسایی و پروسة تعیین انواع که در آن، محل قرارگیری انواع مختلف بکار رفته در برنامه مشخص می‌شود را، اجرا می‌کند. اسمبلی شناسایی شده در پروسة Loader بارگذاری می‌گردد.
دانلود فایل بهینهسازی و پردازش پرس و جو
| دسته بندی | کامپیوتر و IT |
| بازدید ها | 9 |
| فرمت فایل | doc |
| حجم فایل | 458 کیلو بایت |
| تعداد صفحات فایل | 68 |
بهینهسازی و پردازش پرس و جو
در این تحقیق ما به تکنیک‌های بکار رفته توسط DMBS برای پردازش، بهینهسازی و اجرای پرس و جوهای سطح بالا می‌پردازیم. پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه . معتبر شود. پویشگر (اسکنر) علامت هر زبان، مثل لغات کلیدی SQL، اساس ویژگی، و اساس رابطه، را در متن پرس و جو شناسایی می‌کند، در عوض تجربه کننده، ساختار دستوری پرس و جو را برای تعیین اینکه آیا بر طبق قوانین دستوری زبان پرس و جو تدوین می‌شود یا خیر، چک می‌کند. پرس و جو باید همچنین معتبر شود، با چک کردن اینکه تمام اسامی رابطه و ویژگی معتبر هستند و اسامی معنی‌دار در طرح پایگاه اطلاعاتی ویژها‌ی پرس و جو میشوند. نمونه داخلی پرس و جو ایجاد می‌شود، که تحت عنوان ساختار داده‌های درختی بنام درخت پرس و جو می‌باشد. ارائه پرس و جو با استفاده از ساختار داده‌های گراف بنام گراف پرس و جو نیز امکان پذیر است. DOMS باید استراتژی اجرایی برای بازیابی نتیجه پرس و جو از فایل‌های پایگاه اطلاعاتی را هدایت کند. پرس و جو استراتژیهای اجرایی بسیاری دارد. و مرحلة انتخاب، مورد مناسبی برای پردازش پرس وجو تحت عنوان بهینهسازی پرس و جو شناخته شده است. تصویر 1، مراحل مختلف پردازش پرس و جوی سطح بالا را نشان میدهد. قطعه بر نامه بهینه‌ساز پرس وجو، وظیفه ایجاد طرح اجرایی را بعهده دارد و ژنراتور (تولید کننده) که ، کد را برای اجرای آن طرح ایجاد می‌کند. پردازنده پایگاه اطلاعاتی زمان اجرا وظیفه اجرای که پرس و جو را بعهده دارد، خواه در وضعیت کامپایل شده یا تفسیر شده جهت ایجاد نتیجه پرس و جو. اگر خطای زمان اجرا نتیجه شود، پیام خطا توسط پایگاه اطلاعاتی زمان اجرا ایجاد می‌شود.
اصطلاح بهینهسازی نام بی مسمایی است چون در بعضی موارد، طرح اجرایی انتخاب شده، استراتژی بهینه نمی‌باشد، آن فقط استراتژی کارآمد معقول برای اجرای پرس و جو است. یافتن استراتژی بهینه، ضامن صرف زمان زیادی است، بجز برای ساده‌ترین پرس و جوها، ممکن است به اطلاعاتی روی چگونگی اجرای فایل‌ها در فهرست‌های فایل‌ها، اطلاعاتی که ممکن است کاملاً در کاتالوگ DBMS در دسترس نباشد، نیاز باشد. از اینرو، برنامه‌ریزی استراتژی اجرا ممکن است توصیف درست‌تری نسبت به بهینهسازی پرس و جو باشد. برای زبانهای پایگاه اطلاعاتی (دریایی) جهت‌یابی در سطح پایینتر در سیستمهای قانونی، مثل شبکه DML شبکه‌ای یا MOML سلسله مراتبی، برنامه نویس باید، استراتی اجرای پذیرش و جو را انتخاب کند ضمن اینکه برنامه پایگاه اطلاعاتی را می‌نویسد. اگر DBMS فقط زیان جهت‌یابی را ارائه دهد. فرصت و نیاز محدودی برای بهینهسازی پرس وجوی وسیع توسط DBMS وجود دارد، در عوض به برنامه نویس قابلیت انتخاب استراتژی اجرایی بهینه ارائه می‌شود. بعبارت دیگر، زبان پرس و جو در سطح بالا، مثل SQL برای DBMSهای رابطهای یا OQL برای DBMSهای مقصد، در ماهیت تفریطی‌تر است. چون آنچه نتایج مورد نظر پرس و جو است بغیر از شناسایی جزئیات چگونگی بدست آمدن نتیجه، را تعیین می‌کند. بهینهسازی پرس و جو برای پرس و جوهایی ضروی است که در زبان پرس و جوی سطح بالا تعیین می شوند. ما روی توصیف بهینهسازی پرس و جو در زمینه ROBMS تمرکز می‌کنیم چون بسیاری از تکنیک‌هایی که توصیف می کنیم برای، برای ODBMSها تطبیق یافته‌اند. DBMS رابطهای باید استراتژیهای اجرای پرس و جوی دیگری را ارزیابی کند و استراتژی بهینه یا کارآمد معقولی را انتخاب کند. هر DBMS ، تعدادی الگاریتم دسترسی به پایگاه اطلاعاتی کلی دارد که علامتهای رابطهای مثل SELECT یا JOIN یا ترکیبی از این عملیات ها را اجرا می‌کند. تنها استراتژیهای اجرایی که می‌توانند توسط الگاریتم‌های دسترسی DBMS اجرا شوند و برای طراحی پایگاه اطلاعاتی فیزیکی ویژه و پرس و جوی خاص بکار روند، می‌توانند توسط قطعه برنامه بهینهسازی پرس و جو در نظر گرفته شوند. ما با بحث کلی چگونگی ترجمه پرس و جوهای SQL به پرس و جوهای جبری رابطهای و در بهینه‌شدن آنها کار را شروع می‌کنیم. بعد ما روی الگاریتم‌ها برای اجرای عملیاتهای رابطهای در بخش 1802 بحث می‌کنیم. بدنبال این مطلب، بررسی از استراتژیهای بهینهسازی پرس و جو را ارائه می‌دهیم. دو تکنیک اصلی برای اجرای بهینهسازی پرس و جو وجود دارد. اولین تکنیک بر اساس قوانین ذهنی جهت ترتیب دادن عملیات‌ها در استراتژی اجرای پرس و جو می‌باشد. ذهن قانونی است که بخوبی در اکثر موارد عمل می‌کند ولی برای کار مناسب در هر مورد کنش تضمین نمی‌شود. قوانین عملیات‌ها را در درخت پرس وجو مجدداً ترتیب می‌دهند. دومین تکنیک شامل برآورد هزینه استراتژیهای اجرای متفاوت و انتخاب طرح اجرایی با پایین‌ترین هزینه برآورد است. دو تکنیک معمولاً در بهینه ساز پرس و جو (باهم ترکیب میشوند) بهم ملحق می‌گردند. بررسی مختصری از عوامل در نظر گرفته شده در طول بهینهسازی پرس و جو در RDBMS بازرگانی ORACLL= را ارائه می‌دهیم. در بخش بعدی نوعی بهینهسازی پرس و جوی معنایی را ارائه میدهد که در آن محدودیت‌های شناخته شده برای پرداختن به استراتژیهای اجرایی پرس و جوی کارآمد استفاده میشوند. 2 – ترجمه پرس و جوهای SQL به پرس و جوهای رابطهای: در عمل، SQL زبان پرس وجویی است که در اکثر RDBMS های بازرگانی استفاده می‌شود. پرس وجوی SQL ، ابتدا به عبارت جبری رابطهای توسعه یافته معادل، نمایانگر ساختار داروهای درخت پرس و جو، ترجمه می‌شود و بعد بهینهسازی می‌شود. پرس و جوهای SQL به بلوکهای پرس و جو تجزیه میشوند، که واحدهای اساسی را تشکیل می‌دهند که می‌توانند به عملکردهای جبری ترجمه شوند و بهینهسازی شوند. بلوک پرس و جو شامل عبارت SELECT- FROM-WHERE تکی و بندهای Groop By و HAVING است چنانچه این‌ها بخشی از بلوک باشند. از اینرو، پرس و جوهای تو در تو در پرس و جو بعنوان بلوکهای پرس و جوی مجزا شناسایی میشوند. چون SQL شامل عملکردهای گروهی، مثل MAX ، COUNT,SUM می‌باشد، این عملگرها باید در پرس و جوی جبری توسعه یافته‌ای شامل شوند، همانطوریکه در بخش 705 توصیف شد. پرس و جوی SQL در رابطه EMPLOEE در تصویر 705 را در نظر بگیرید: این پرس و جو شامل، پرس و جوی فرعی تو در تو است و از اینرو به دو بلوک تجزیه می‌شود. بلوک درونی بدین صورت است: و بلوک بیرونی بدین صورت می باشد: که C نمایانگر نتیجه حاصله از بلوک درونی است. بلوک درونی به عبارت جبری رابطهای توسعه یافته زیر ترجمه شده است: و بلوک بیرونی به عبارت زیر ترجمه شده است: بهینه‌ساز پرس و جو، طرح اجرایی را برای هر بلوک انتخاب می‌کند. ما باید اشاره کنیم به در مثال فوق، بلوک درونی نیاز به ارزیابی شدن دارد تنها زمانی که، حداکثرحقوقی که بعکار می‌رود که بعنوان ثابت C، توسط بلوک بیرونی استفاده می‌شود. ما اینرو پرس و جوی تودرتوی غیرمرتبط نامیدیم (در فصل 8). آن برای بهینهسازی پرس و جوهای تو در توی مرتبط پیچیده‌تر، خیلی سخت‌تر است، جایی که متغیر Tuple از بلوک بیرونی در بند WHERE در بلوک درونی ظاهر می‌شود. 1802- الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو: RDBMS شامل الگاریتم‌هایی برای اجرای انواع مختلف عملیاتهای رابطهای است که می‌توانند در استراتژی اجرای پرس و جو نمایان شوند، این عملیات‌ها شامل عملیاتهای جبری بیسیک (اصلی) و توسعه یافته مورد بحث در فصل 7 ، و در بسیاری موارد، الحاقاتی از این عملیات‌ها می‌باشد. برای هر یک از این عملیات ها یا الحاقی از عملیات‌ها، یک یا چند الگاریتم برای اجرای عملیات‌ها در دسترس قرار دارند. الگاریتم ممکن است فقط برای ساختارهای ذخیره خاص مسیرهای دستیابی بکار روند، در اینصورت ، تنها در صورتی استفاده می‌شود که فایل های موجود در عملیات شامل این مسیرهای دستیابی هستند. در این بخش، ما به الگاریتم‌های نمونه بکار رفته برای اجرای SEKECT ، JOIN و دیگر عملیاتهای رابطهای می‌پردازیم. ما بحث مرتب کردن خارجی را در بخش 180201 آغاز می‌کنیم که در قلب عملیاتهای رابطهای قرار دارد که از استراتژیهای ادغام کردن به مرتب کردن استفاده می‌کند. بعد ما به الگاریتم‌هایی برای اجرای عملیات SELECT در بخش 180202 می‌پردازیم، به عملیات JOIN در بخش 180203 و عملیات PRIJECT و عملیاتهای مجموعه در بخش IE 1802 و عملیاتهای گروهی و جمعی در بخش 2 .2 . 18 می‌پردازیم. 1. 2. 18- مرتب کردن خارجی: مرتب کردن، یکی از الگاریتم‌های اولیه بکار رفته در پردازش پرس و جو است. برای مثال، به هر وقت پرس و جوی SQL ، بعد ORDER BY را تعیین می‌کند، نتیجه پرس و جو باید مرتب گردد. مرتب کردن، مؤلفه کلیدی در الگاریتم‌های مرتب کردن- ادغام کردن (مرتب-ادغام) بکار رفته برای Join و عملیاتهای دیگر، دور الگاریتم‌های حذف کپی برای عملیات PROYECT است. ما روی بعضی از این الگاریتم‌ها در بخش 3. 2. 18 و 4. 02 18 بحث خواهیم کرد. توجه کنید که مرتب کردن در صورتی که اجتناب می‌شود که شاخص مناسب برای امکان دسترسی مرتب شده به ثبت‌ها وجود دارد. مرتب کردن خارجی به الگاریتم‌های مرتب کردن اشاره می‌کند که برای فایل های بزرگ ثبت های ذخیره شده روی دیسک مناسب هستند که در حافظه اصلی، مثل اکثر فایل های پایگاه اطلاعاتی تناسب نمی‌‌یابد. الگاریتم مرتب کردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌کند، که با مرتب کردن- فایل‌های فرعی کوچک بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام میشوند، فایل‌های فرعی مرتب شده بزرگتری ایجاد میشوند که بترتیب ادغام میشوند. الگاریتم ادغام –مرتب، مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد، جایی که مرتب کردن واقعی و ادغام اجراها انجام می شود. الگاریتم اصلی (سیبک) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب کردن و (2) مرحله ادغام.در مرحله مرتب کردن، اجراهای فایلی که می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده میشوند و با استفاده از الگاریتم مرتب کردن داخلی مرتب می‌شود عقب دیسک بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود. اندازه اجرا و تعداد اجراهای آغازین توسط تعداد بلوکهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود. برای مثال اگر بلوکو اندازه قایل 1024=b بلوک باشد، بعد یا 205 اجرای آغازین در هر اندازه 5 بلوک است. از اینرو، بعد از مرحله مرتب کردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسک ذخیره میشوند. اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسک ذخیره میشوند. در مرحله ادغام شدن، اجراهای مرتب شده، در طول یک یا چند گذر ادغام میشوند. درجه ادغام شدن تعداد اجراهایی است که می‌توانند با همدیگر در هر گذر ادغام شوند. در هر گذر، یک بلوک بافر، برای حفظ یک بلوک از هر اجرای ادغام شده نیاز می‌باشد، و یک بلوک برای تشکیل یک بلوک نتیجه ادغام لازم است . از اینرو، کوچکتر از و است و تعداد گذرها، است. در مثالها، است. لذا، 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: که بعد به 12، بعد 4 بعد یک اجرا ادغام میشوند، که بدین معنی است که چهارگذر لازم می‌باشد. حداقل از 2، عملکرد بدترین مورد الگاریتم را ارائه میدهد که بدین قرار است: اولین جمله، تعداد دسترسی‌های بلوک برای مرحله مرتب سازی را نشان میدهد، چون هر بلوک فایل دو برابر دسترسی می‌شود، یکبار برای خواندن در حافظه، یکبار برای نوشتن ثبت‌ها دیسک بعد از مرتب کردن. دومین جمله، تعداد دسترسی‌های بلوک برای مرحله ادغام کردن را نشان میدهد، با فرض اینکه بدترین مورد از 2 وجود دارد. بطور کلی، ثبت وقایع در مبنای و عبارت برای تعداد دسترسی‌های بلوک نوین قرار می‌شود: تصویر 1802- شرح الگاریتم ادغام – مرتب کردن برای مرتب کردن خارجی: 2. 2. 18- اجرا و پیاده‌سازی عملیات SELECT : تعداد Optionهایی ( انتخاب‌ها) برای اجرای عملیات SELECT وجود دارد، که بعضی به فایل دارای مسیرهای دستیابی خاص بستگی دارند و تنها برای انواع معین شرایط انتخاب بکار می‌رود. ما به الگاریتم‌هایی جهت اجرای SELECT در این بخش می‌پردازیم. ما از عملیاتهای زیر استفاده می‌کنیم که روی پایگاه اطلاعاتی رابطهای در تصویر 507 مشخص شده و بحث ما را روشن می‌سازد: متدهای جستجو برای انتخاب ساده: تعدادی الگاریتم های جستجو برای انتخاب ثبت‌ها از فایل امکان‌پذیر می‌باشند، چون ثبتهای فایل نامیده می شوند، چون ثبتهای فایل را برای جستجو و بازیابی ثبت‌هایی که شرایط انتخاب را برآورده می‌سازند، پویش می‌کنند. اگر الگاریتم جستجو شامل کاربرد شاخص باشد، جستحوی شاخص پویش شاخص نامیده می‌شد. متدهای جستجوی زیر ( 1S تا s6 ) مثالهایی از الگاریتم‌های جستجو هستند که می‌توانند برای اجرای عملیات انتخاب بکار روند: - s1 : جستجوی خطی (روش برنامه‌سازی پر قدرت): بازیابی هر ثبت در فایل، و تست اینکه آیا مقادیر ویژگی آن، شرط انتخاب را براورده می‌سازد یا خیر. - S2: جستجوی بنیادی (دودویی): اگر شرط انخاب شامل قیاس تساوی روی ویژگی کلیدی باشد که روی آن فایل مرتب می‌شود، جستجوی بنیادی، که نسبت به جستجوی خطی کارآمدتر است، می‌تواند بکار رود. مثال OP1 است چنانچه ssn ، ویژگی کلیدی با شاخص اولیه( یا کلید hash) باشد، برای مثال، SNN-‘123456789’ در opt، شاخص اولیه یا کلید hosh) برای بازیابی ثبت استفاده می‌شود، توجه کنید که این شرط، ثبت تکی را بازیابی می‌کند. - S4: کاربرد شاخص اولیه برای بازیابی ثبتهای متعدد: اگر شرط انتخاب شدن قیاس تساوی روی ویژگی غیر کلیدی با شاخص خدشه‌سازی باشد، برای مثال در ، شاخص را برای بازیابی کل ثبت‌ها در برآورده ساختن شرط، استفاده کنید. - S6: بکارگیری شاخص ثانویه (درخت ) روی قیاس تساوی: این متد جستجو می‌تواند برای بازیابی ثبت تکی بکار رود چنانچه فیلد نمایه‌سازی (شاخص‌سازی) کلید باشد یا برای بازیابی ثبتهای متعدد بکار می‌رود چنانچه فیلد شاخص‌سازی کلید نباشد، این می‌تواند برای مقایساتی شامل یا بکار رود. در بخش 3. 4. 18، ما به چگونگی توسعه فرمول‌هایی می‌پردازیم که هزینه‌دستیابی این متدهای جستجو را در اصطلاحات تعداد دستیابی‌های بلوک و زمان دستیابی برآورد می‌کند. Method S!برای هر فایلی استفاده می‌شود ولی تمام متدهای دیگر به داشتن مسیر دستیابی مناسب روی ویژگی‌بکار رفته در شرط انتخاب بستگی دارند. متدهای S4 و 6، می‌توانند برای بازیابی ثبت‌ها در دامنه معین بکار روند برای مثال پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به میشوند.متدهای جستجو برای انتخاب پیچیده: اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشکیل شود، DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده کند: S7: انتخاب تقارنی یا ارتباطی با استفاده از شاخص اختصاص: اگر ویژگی شامل شده در هر شرط ساده متکی در شرط تقارنی، مسیر دستیابی داشته باشد که به کاربرد یکی از متدهای S2 تا S6 امکان عمل دهد، از آن شرط برای بازیابی ثبتهای استفاده کنید و بعد کنترل کنید آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌کند یا خیر. S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مرکب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مرکب در فیلدهای مرکب وجود داشته باشد، برای مثال اگر شاخص روی کلید مرکب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره کرد.
در این تحقیق ما به تکنیک‌های بکار رفته توسط DMBS برای پردازش، بهینهسازی و اجرای پرس و جوهای سطح بالا می‌پردازیم. پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه . معتبر شود. پویشگر (اسکنر) علامت هر زبان، مثل لغات کلیدی SQL، اساس ویژگی، و اساس رابطه، را در متن پرس و جو شناسایی می‌کند، در عوض تجربه کننده، ساختار دستوری پرس و جو را برای تعیین اینکه آیا بر طبق قوانین دستوری زبان پرس و جو تدوین می‌شود یا خیر، چک می‌کند. پرس و جو باید همچنین معتبر شود، با چک کردن اینکه تمام اسامی رابطه و ویژگی معتبر هستند و اسامی معنی‌دار در طرح پایگاه اطلاعاتی ویژها‌ی پرس و جو میشوند. نمونه داخلی پرس و جو ایجاد می‌شود، که تحت عنوان ساختار داده‌های درختی بنام درخت پرس و جو می‌باشد. ارائه پرس و جو با استفاده از ساختار داده‌های گراف بنام گراف پرس و جو نیز امکان پذیر است. DOMS باید استراتژی اجرایی برای بازیابی نتیجه پرس و جو از فایل‌های پایگاه اطلاعاتی را هدایت کند. پرس و جو استراتژیهای اجرایی بسیاری دارد. و مرحلة انتخاب، مورد مناسبی برای پردازش پرس وجو تحت عنوان بهینهسازی پرس و جو شناخته شده است. تصویر 1، مراحل مختلف پردازش پرس و جوی سطح بالا را نشان میدهد. قطعه بر نامه بهینه‌ساز پرس وجو، وظیفه ایجاد طرح اجرایی را بعهده دارد و ژنراتور (تولید کننده) که ، کد را برای اجرای آن طرح ایجاد می‌کند. پردازنده پایگاه اطلاعاتی زمان اجرا وظیفه اجرای که پرس و جو را بعهده دارد، خواه در وضعیت کامپایل شده یا تفسیر شده جهت ایجاد نتیجه پرس و جو. اگر خطای زمان اجرا نتیجه شود، پیام خطا توسط پایگاه اطلاعاتی زمان اجرا ایجاد می‌شود. اصطلاح بهینهسازی نام بی مسمایی است چون در بعضی موارد، طرح اجرایی انتخاب شده، استراتژی بهینه نمی‌باشد، آن فقط استراتژی کارآمد معقول برای اجرای پرس و جو است. یافتن استراتژی بهینه، ضامن صرف زمان زیادی است، بجز برای ساده‌ترین پرس و جوها، ممکن است به اطلاعاتی روی چگونگی اجرای فایل‌ها در فهرست‌های فایل‌ها، اطلاعاتی که ممکن است کاملاً در کاتالوگ DBMS در دسترس نباشد، نیاز باشد. از اینرو، برنامه‌ریزی استراتژی اجرا ممکن است توصیف درست‌تری نسبت به بهینهسازی پرس و جو باشد. برای زبانهای پایگاه اطلاعاتی (دریایی) جهت‌یابی در سطح پایینتر در سیستمهای قانونی، مثل شبکه DML شبکه‌ای یا MOML سلسله مراتبی، برنامه نویس باید، استراتی اجرای پذیرش و جو را انتخاب کند ضمن اینکه برنامه پایگاه اطلاعاتی را می‌نویسد. اگر DBMS فقط زیان جهت‌یابی را ارائه دهد. فرصت و نیاز محدودی برای بهینهسازی پرس وجوی وسیع توسط DBMS وجود دارد، در عوض به برنامه نویس قابلیت انتخاب استراتژی اجرایی بهینه ارائه می‌شود. بعبارت دیگر، زبان پرس و جو در سطح بالا، مثل SQL برای DBMSهای رابطهای یا OQL برای DBMSهای مقصد، در ماهیت تفریطی‌تر است. چون آنچه نتایج مورد نظر پرس و جو است بغیر از شناسایی جزئیات چگونگی بدست آمدن نتیجه، را تعیین می‌کند. بهینهسازی پرس و جو برای پرس و جوهایی ضروی است که در زبان پرس و جوی سطح بالا تعیین می شوند. ما روی توصیف بهینهسازی پرس و جو در زمینه ROBMS تمرکز می‌کنیم چون بسیاری از تکنیک‌هایی که توصیف می کنیم برای، برای ODBMSها تطبیق یافته‌اند. DBMS رابطهای باید استراتژیهای اجرای پرس و جوی دیگری را ارزیابی کند و استراتژی بهینه یا کارآمد معقولی را انتخاب کند. هر DBMS ، تعدادی الگاریتم دسترسی به پایگاه اطلاعاتی کلی دارد که علامتهای رابطهای مثل SELECT یا JOIN یا ترکیبی از این عملیات ها را اجرا می‌کند. تنها استراتژیهای اجرایی که می‌توانند توسط الگاریتم‌های دسترسی DBMS اجرا شوند و برای طراحی پایگاه اطلاعاتی فیزیکی ویژه و پرس و جوی خاص بکار روند، می‌توانند توسط قطعه برنامه بهینهسازی پرس و جو در نظر گرفته شوند. ما با بحث کلی چگونگی ترجمه پرس و جوهای SQL به پرس و جوهای جبری رابطهای و در بهینه‌شدن آنها کار را شروع می‌کنیم. بعد ما روی الگاریتم‌ها برای اجرای عملیاتهای رابطهای در بخش 1802 بحث می‌کنیم. بدنبال این مطلب، بررسی از استراتژیهای بهینهسازی پرس و جو را ارائه می‌دهیم. دو تکنیک اصلی برای اجرای بهینهسازی پرس و جو وجود دارد. اولین تکنیک بر اساس قوانین ذهنی جهت ترتیب دادن عملیات‌ها در استراتژی اجرای پرس و جو می‌باشد. ذهن قانونی است که بخوبی در اکثر موارد عمل می‌کند ولی برای کار مناسب در هر مورد کنش تضمین نمی‌شود. قوانین عملیات‌ها را در درخت پرس وجو مجدداً ترتیب می‌دهند. دومین تکنیک شامل برآورد هزینه استراتژیهای اجرای متفاوت و انتخاب طرح اجرایی با پایین‌ترین هزینه برآورد است. دو تکنیک معمولاً در بهینه ساز پرس و جو (باهم ترکیب میشوند) بهم ملحق می‌گردند. بررسی مختصری از عوامل در نظر گرفته شده در طول بهینهسازی پرس و جو در RDBMS بازرگانی ORACLL= را ارائه می‌دهیم. در بخش بعدی نوعی بهینهسازی پرس و جوی معنایی را ارائه میدهد که در آن محدودیت‌های شناخته شده برای پرداختن به استراتژیهای اجرایی پرس و جوی کارآمد استفاده میشوند. 2 – ترجمه پرس و جوهای SQL به پرس و جوهای رابطهای: در عمل، SQL زبان پرس وجویی است که در اکثر RDBMS های بازرگانی استفاده می‌شود. پرس وجوی SQL ، ابتدا به عبارت جبری رابطهای توسعه یافته معادل، نمایانگر ساختار داروهای درخت پرس و جو، ترجمه می‌شود و بعد بهینهسازی می‌شود. پرس و جوهای SQL به بلوکهای پرس و جو تجزیه میشوند، که واحدهای اساسی را تشکیل می‌دهند که می‌توانند به عملکردهای جبری ترجمه شوند و بهینهسازی شوند. بلوک پرس و جو شامل عبارت SELECT- FROM-WHERE تکی و بندهای Groop By و HAVING است چنانچه این‌ها بخشی از بلوک باشند. از اینرو، پرس و جوهای تو در تو در پرس و جو بعنوان بلوکهای پرس و جوی مجزا شناسایی میشوند. چون SQL شامل عملکردهای گروهی، مثل MAX ، COUNT,SUM می‌باشد، این عملگرها باید در پرس و جوی جبری توسعه یافته‌ای شامل شوند، همانطوریکه در بخش 705 توصیف شد. پرس و جوی SQL در رابطه EMPLOEE در تصویر 705 را در نظر بگیرید: این پرس و جو شامل، پرس و جوی فرعی تو در تو است و از اینرو به دو بلوک تجزیه می‌شود. بلوک درونی بدین صورت است: و بلوک بیرونی بدین صورت می باشد: که C نمایانگر نتیجه حاصله از بلوک درونی است. بلوک درونی به عبارت جبری رابطهای توسعه یافته زیر ترجمه شده است: و بلوک بیرونی به عبارت زیر ترجمه شده است: بهینه‌ساز پرس و جو، طرح اجرایی را برای هر بلوک انتخاب می‌کند. ما باید اشاره کنیم به در مثال فوق، بلوک درونی نیاز به ارزیابی شدن دارد تنها زمانی که، حداکثرحقوقی که بعکار می‌رود که بعنوان ثابت C، توسط بلوک بیرونی استفاده می‌شود. ما اینرو پرس و جوی تودرتوی غیرمرتبط نامیدیم (در فصل 8). آن برای بهینهسازی پرس و جوهای تو در توی مرتبط پیچیده‌تر، خیلی سخت‌تر است، جایی که متغیر Tuple از بلوک بیرونی در بند WHERE در بلوک درونی ظاهر می‌شود. 1802- الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو: RDBMS شامل الگاریتم‌هایی برای اجرای انواع مختلف عملیاتهای رابطهای است که می‌توانند در استراتژی اجرای پرس و جو نمایان شوند، این عملیات‌ها شامل عملیاتهای جبری بیسیک (اصلی) و توسعه یافته مورد بحث در فصل 7 ، و در بسیاری موارد، الحاقاتی از این عملیات‌ها می‌باشد. برای هر یک از این عملیات ها یا الحاقی از عملیات‌ها، یک یا چند الگاریتم برای اجرای عملیات‌ها در دسترس قرار دارند. الگاریتم ممکن است فقط برای ساختارهای ذخیره خاص مسیرهای دستیابی بکار روند، در اینصورت ، تنها در صورتی استفاده می‌شود که فایل های موجود در عملیات شامل این مسیرهای دستیابی هستند. در این بخش، ما به الگاریتم‌های نمونه بکار رفته برای اجرای SEKECT ، JOIN و دیگر عملیاتهای رابطهای می‌پردازیم. ما بحث مرتب کردن خارجی را در بخش 180201 آغاز می‌کنیم که در قلب عملیاتهای رابطهای قرار دارد که از استراتژیهای ادغام کردن به مرتب کردن استفاده می‌کند. بعد ما به الگاریتم‌هایی برای اجرای عملیات SELECT در بخش 180202 می‌پردازیم، به عملیات JOIN در بخش 180203 و عملیات PRIJECT و عملیاتهای مجموعه در بخش IE 1802 و عملیاتهای گروهی و جمعی در بخش 2 .2 . 18 می‌پردازیم. 1. 2. 18- مرتب کردن خارجی: مرتب کردن، یکی از الگاریتم‌های اولیه بکار رفته در پردازش پرس و جو است. برای مثال، به هر وقت پرس و جوی SQL ، بعد ORDER BY را تعیین می‌کند، نتیجه پرس و جو باید مرتب گردد. مرتب کردن، مؤلفه کلیدی در الگاریتم‌های مرتب کردن- ادغام کردن (مرتب-ادغام) بکار رفته برای Join و عملیاتهای دیگر، دور الگاریتم‌های حذف کپی برای عملیات PROYECT است. ما روی بعضی از این الگاریتم‌ها در بخش 3. 2. 18 و 4. 02 18 بحث خواهیم کرد. توجه کنید که مرتب کردن در صورتی که اجتناب می‌شود که شاخص مناسب برای امکان دسترسی مرتب شده به ثبت‌ها وجود دارد. مرتب کردن خارجی به الگاریتم‌های مرتب کردن اشاره می‌کند که برای فایل های بزرگ ثبت های ذخیره شده روی دیسک مناسب هستند که در حافظه اصلی، مثل اکثر فایل های پایگاه اطلاعاتی تناسب نمی‌‌یابد. الگاریتم مرتب کردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌کند، که با مرتب کردن- فایل‌های فرعی کوچک بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام میشوند، فایل‌های فرعی مرتب شده بزرگتری ایجاد میشوند که بترتیب ادغام میشوند. الگاریتم ادغام –مرتب، مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد، جایی که مرتب کردن واقعی و ادغام اجراها انجام می شود. الگاریتم اصلی (سیبک) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب کردن و (2) مرحله ادغام.در مرحله مرتب کردن، اجراهای فایلی که می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده میشوند و با استفاده از الگاریتم مرتب کردن داخلی مرتب می‌شود عقب دیسک بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود. اندازه اجرا و تعداد اجراهای آغازین توسط تعداد بلوکهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود. برای مثال اگر بلوکو اندازه قایل 1024=b بلوک باشد، بعد یا 205 اجرای آغازین در هر اندازه 5 بلوک است. از اینرو، بعد از مرحله مرتب کردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسک ذخیره میشوند. اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسک ذخیره میشوند. در مرحله ادغام شدن، اجراهای مرتب شده، در طول یک یا چند گذر ادغام میشوند. درجه ادغام شدن تعداد اجراهایی است که می‌توانند با همدیگر در هر گذر ادغام شوند. در هر گذر، یک بلوک بافر، برای حفظ یک بلوک از هر اجرای ادغام شده نیاز می‌باشد، و یک بلوک برای تشکیل یک بلوک نتیجه ادغام لازم است . از اینرو، کوچکتر از و است و تعداد گذرها، است. در مثالها، است. لذا، 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: که بعد به 12، بعد 4 بعد یک اجرا ادغام میشوند، که بدین معنی است که چهارگذر لازم می‌باشد. حداقل از 2، عملکرد بدترین مورد الگاریتم را ارائه میدهد که بدین قرار است: اولین جمله، تعداد دسترسی‌های بلوک برای مرحله مرتب سازی را نشان میدهد، چون هر بلوک فایل دو برابر دسترسی می‌شود، یکبار برای خواندن در حافظه، یکبار برای نوشتن ثبت‌ها دیسک بعد از مرتب کردن. دومین جمله، تعداد دسترسی‌های بلوک برای مرحله ادغام کردن را نشان میدهد، با فرض اینکه بدترین مورد از 2 وجود دارد. بطور کلی، ثبت وقایع در مبنای و عبارت برای تعداد دسترسی‌های بلوک نوین قرار می‌شود: تصویر 1802- شرح الگاریتم ادغام – مرتب کردن برای مرتب کردن خارجی: 2. 2. 18- اجرا و پیاده‌سازی عملیات SELECT : تعداد Optionهایی ( انتخاب‌ها) برای اجرای عملیات SELECT وجود دارد، که بعضی به فایل دارای مسیرهای دستیابی خاص بستگی دارند و تنها برای انواع معین شرایط انتخاب بکار می‌رود. ما به الگاریتم‌هایی جهت اجرای SELECT در این بخش می‌پردازیم. ما از عملیاتهای زیر استفاده می‌کنیم که روی پایگاه اطلاعاتی رابطهای در تصویر 507 مشخص شده و بحث ما را روشن می‌سازد: متدهای جستجو برای انتخاب ساده: تعدادی الگاریتم های جستجو برای انتخاب ثبت‌ها از فایل امکان‌پذیر می‌باشند، چون ثبتهای فایل نامیده می شوند، چون ثبتهای فایل را برای جستجو و بازیابی ثبت‌هایی که شرایط انتخاب را برآورده می‌سازند، پویش می‌کنند. اگر الگاریتم جستجو شامل کاربرد شاخص باشد، جستحوی شاخص پویش شاخص نامیده می‌شد. متدهای جستجوی زیر ( 1S تا s6 ) مثالهایی از الگاریتم‌های جستجو هستند که می‌توانند برای اجرای عملیات انتخاب بکار روند: - s1 : جستجوی خطی (روش برنامه‌سازی پر قدرت): بازیابی هر ثبت در فایل، و تست اینکه آیا مقادیر ویژگی آن، شرط انتخاب را براورده می‌سازد یا خیر. - S2: جستجوی بنیادی (دودویی): اگر شرط انخاب شامل قیاس تساوی روی ویژگی کلیدی باشد که روی آن فایل مرتب می‌شود، جستجوی بنیادی، که نسبت به جستجوی خطی کارآمدتر است، می‌تواند بکار رود. مثال OP1 است چنانچه ssn ، ویژگی کلیدی با شاخص اولیه( یا کلید hash) باشد، برای مثال، SNN-‘123456789’ در opt، شاخص اولیه یا کلید hosh) برای بازیابی ثبت استفاده می‌شود، توجه کنید که این شرط، ثبت تکی را بازیابی می‌کند. - S4: کاربرد شاخص اولیه برای بازیابی ثبتهای متعدد: اگر شرط انتخاب شدن قیاس تساوی روی ویژگی غیر کلیدی با شاخص خدشه‌سازی باشد، برای مثال در ، شاخص را برای بازیابی کل ثبت‌ها در برآورده ساختن شرط، استفاده کنید. - S6: بکارگیری شاخص ثانویه (درخت ) روی قیاس تساوی: این متد جستجو می‌تواند برای بازیابی ثبت تکی بکار رود چنانچه فیلد نمایه‌سازی (شاخص‌سازی) کلید باشد یا برای بازیابی ثبتهای متعدد بکار می‌رود چنانچه فیلد شاخص‌سازی کلید نباشد، این می‌تواند برای مقایساتی شامل یا بکار رود. در بخش 3. 4. 18، ما به چگونگی توسعه فرمول‌هایی می‌پردازیم که هزینه‌دستیابی این متدهای جستجو را در اصطلاحات تعداد دستیابی‌های بلوک و زمان دستیابی برآورد می‌کند. Method S!برای هر فایلی استفاده می‌شود ولی تمام متدهای دیگر به داشتن مسیر دستیابی مناسب روی ویژگی‌بکار رفته در شرط انتخاب بستگی دارند. متدهای S4 و 6، می‌توانند برای بازیابی ثبت‌ها در دامنه معین بکار روند برای مثال پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به میشوند.متدهای جستجو برای انتخاب پیچیده: اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشکیل شود، DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده کند: S7: انتخاب تقارنی یا ارتباطی با استفاده از شاخص اختصاص: اگر ویژگی شامل شده در هر شرط ساده متکی در شرط تقارنی، مسیر دستیابی داشته باشد که به کاربرد یکی از متدهای S2 تا S6 امکان عمل دهد، از آن شرط برای بازیابی ثبتهای استفاده کنید و بعد کنترل کنید آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌کند یا خیر. S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مرکب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مرکب در فیلدهای مرکب وجود داشته باشد، برای مثال اگر شاخص روی کلید مرکب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره کرد.
دانلود فایل تحلیل الگوریتم شاخه و قید موازی آسنکرون
| دسته بندی | کامپیوتر و IT |
| بازدید ها | 12 |
| فرمت فایل | doc |
| حجم فایل | 28 کیلو بایت |
| تعداد صفحات فایل | 32 |
تحلیل الگوریتم شاخه و قید موازی آسنکرون
1- خلاصه:
در این مقاله توضیحی درباره کامپیوترهای موازی می‌دهیم و بعد الگوریتمهای موازی را بررسی می‌کنیم. ویژگیهای الگوریتم branch & bound را بیان می‌کنیم و الگوریتمهای b&b موازی را ارائه می‌دهیم و دسته‌ای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه می‌دهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی می‌کنیم.
نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازی‌سازی است معرفی می‌کنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازی‌سازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.
2- معرفی:
همیشه نیاز به کامپیوترهای قدرتمند وجود داشته است. در مدل سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک دستورالعمل داده بایستی از محل یک کامپیوتر به محل دیگری منتقل می‌شد، لذا نیاز هب کامپیوترهای قدرتمند اهمیت روز افزون پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این مدل جدید چندین عنصر پردازشی در اجرای یک task واحد با هم همکاری می‌کنند. ایده اصل این مدل بر اساس تقسیم یک task به subtaskهای مستقل از یکدیگر است که می‌توانند هر کدام بصورت parallel (موازی) اجرا شوند. این نوع از کامپیوتر را کامپیوتر موازی گویند.
تا زمانیکه این امکان وجود داشته باشد که یک task را به زیر taskهایی تقسیم کنیم که اندازه بزرگترین زیر task همچنان به گونه‌ای باشد که باز هم بتوان آنرا کاهش داد و البته تا زمانیکه عناصر پردازشی کافی برای اجرای این sub task ها بطور موازی وجود داشته باشد، قدرت محاسبه یک کامپیوتر موازی نامحدود است. اما در عمل این دو شرط بطور کامل برقرار نمی‌شوند:
اولاً: این امکان وجود ندارد که هر taskی را بطور دلخواه به تعدادی زیر taskهای مستقل تقسیم کنیم. چون همواره تعدادی زیر task های وابسته وجود دارد که بایستی بطور خطی اجرا شوند. از اینرو زمان مورد نیاز برای اجرای یک task بطور موازی یک حد پایین دارد.
دوماً: هر کامپیوتر موازی که عملاً ساخته می‌شود شامل تعداد معینی عناصر پردازشی (Processing element) است. به محض آنکه تعداد taskها فراتر از تعداد عناصر پردازشی برود، بعضی از sub task ها بایستی بصورت خطی اجرا شوند و بعنوان یک فاکتور ثابت در تسریع کامپیوتر موازی تصور می‌شود.
الگوریتمهای B&B مسائل بهینه سازی گسسته را به روش تقسیم فضای حالت حل می‌کنند. در تمام این مقاله فرض بر این است که تمام مسائل بهینه سازی مسائل می‌نیمم کردن هستند و منظور از حل یک مسئله پیدا کردن یک حل ممکن با مقدار می‌نیمم است. اگر چندین حل وجود داشته باشد، مهم نیست کدامیک از آنها پیدا شده.
الگوریتم B&B یک مسئله را به زیر مسئله‌های کوچکتر بوسیله تقسیم فضای حالت به زیر فضاهای (Subspace) کوچکتر، تجزیه می‌کند. هر زیر مسئله تولید شده یا حل است و یا ثابت می‌شود که به حل بهینه برای مسئله اصلی (Original) نمی‌انجامد و حذف می‌شود. اگر برای یک زیر مسئله هیچ کدام از این دو امکان بلافاصله استنباط نشود، آن زیر مسئله به زیرمسئله‌های کوچکتر دوباره تجزیه می‌شود. این پروسه آنقدر ادامه پیدا می‌کند تا تمام زیر مسئله‌های تولید شده یا حل شوند یا حذف شوند.
در الگوریتمهای B&B کار انجام شده در حین اجرا به شدت تحت تاثیر نمونه مسئله خاص قرار می‌گیرد. بدون انجام دادن اجرای واقعی الگوریتم این امکان وجود ندارد که تخمین درستی از کار انجام شده بدست آورد. علاوه برآن، روشی که کار باید سازمان‌دهی شود بر روی کار انجام شده تاثیر می‌گذارد. هر گامی که در اجرای الگوریتم b&b ی موازی بطور موفقیت‌آمیزی انجام می‌شود و البته به دانشی است که تاکنون بدست آورده. لذا استفاده از استراتژی جستجوی متفاوت یا انشعاب دادن چندین زیر مسئله بطور موازی باعث بدست آمدن دانشی متفاوت می‌شود پس می‌توان با ترتیب متفاوتی زیر مسئله‌ها را انشعاب داد.
دقت کنید که در یک بدل محاسبه خطی افزایش قدرت محاسبه فقط بر روی تسریع الگوریتم اثر می‌کند وگرنه کار انجام شده همچنان یکسان است.
با این حال اگر قدرت محاسبه یک کامپیوتر موازی با اضافه کردن عناصر پردازشی اضافه افزایش پیدا کند. اجرای الگوریتم b&b بطور آشکاری تغییر می‌کند (به عبارت دیگر ترتیبی که در آن زیر برنامه‌ها انشعاب پیدا می‌کنند تغییر می‌کند). بنابراین حل مسائل بهینهسازی گسسته سرسع بوسیله یک کامپیوتر موازی نه تنها باعث افزایش قدرت محاسبه کامپیوتر موازی شده است بلکه باعث گسترش الگوریتمهای موازی نیز گشته است.
3- کامپیوترهای موازی (Parallel computers):
یکی از مدلهای اصلی محاسبات Control drivenmodel است، در این مدل کاربر باید صریحاً ترتیب انجام عملیات را مشخص کند و آن دسته از عملیاتی که باید به طور موازی اجرا شوند را تعیین کند. این مدل مستقل از عناصر پردازش به صورت زیر تقسیم‌بندی می‌شود:
- کامپیوترهای SISD، که یک عنصر پردازشی وجود دارد و توان انجام فقط یک عمل را در یک زمان دارد.
- کامپیوترهای MIMD، دارای چندین عنصر پردازشی هستند که بطور موازی دستورالعملهای متفاوت را روی دیتاهای متفاوت انجام می‌دهند.
- کامپیوترهای SIMD، همه عناصر پردازشی‌شان یک دستور یکسان را در یک زمان بر روی داده‌های متفاوتی انجام می‌دهند. اگر چه امکان پنهان کردن عناصر پردازشی وجود دارد. عنصر پردازشی پنهان شده نتیجه عملی را که انجام داده ذخیره نمی‌کند.
سیستمهای SIMD بر اساس نحوه ارتباط و اتصال عناصر پردازشی به یکدیگر خود به بخشهایی تقسیم میشوند: اگر تمام عناصر پردازشی به یکدیگر متصل باشند و از طریق یک حافظه مشترک ارتباط داشته باشند، به آن tightly coupled system گویند.
و اگر عناصر پردازش حافظه مشترک نداشته باشند اما از طریق شبکه‌ای بهم متصل باشند و بروش message passing با هم ارتباط داشته باشند، به آن loosely coupled system گویند.
حافظه مشترک در tightly coupled system ها هم نقطه قوت و هم نقطه ضعف این سیستمها است. امکان به اشتراک گذاشتن راحت و سریع اطلاعات بین عناصر پردازشی مختلف را فراهم می‌کند. ارتباط به عملیات ساده read و wite روی حافظه مشترک خلاصه می‌شود و هر عنصر پردازشی مستقیماً با دیگر عناصر پردازشی ارتباط برقرار می‌کند. با این حال، اگر تعداد عناصر پردازشی متصل به حافظه مشترک افزایش یابد، حافظه مشترک تبدیل به گلوگاه (Bottleneck) می‌شود.
بنابراین تعداد عناصر پردازشی در یک سیستم tightly coupled محدود است. به جهت اینکه تمام عناصر پردازشی بایستی به ان حافظه مشترک متصل باشند، این سیستمها بصورت کامل از پیش ساخته هستند و امکان اضافه کردن عناصر پردازش به سیستم وجود ندارد.
از طرف دیگر، ارتباط در یک سیستم loosely coupled کند و آهسته است. تبادل پیامها نیاز به زمانی بیش از زمان لازم برای نوشتن یا خواندن از یک حافظه مشترک دارد. این امکان هم وجود دارد که یک عنصر پردازش مستقیماً به عنصر پردازش دیگر که قصد ارتباط دارد متصل نباشد.
در مقابل compactness بودن سیستمهای tightly coupled ، عناصر پردازشی در یک سیستم loosely coupled می‌توانند در تمام نقاط توزیع شوند. لذا فاصله فیزیکی که یک پیام باید طی کند، بیشتر می‌شود. به جهت این حقیقت که عناصر پردازشی برای ارتباط در یک شبکه از یک پروتکل استفاده می‌کنند، lossely coupled system می‌توانند شامل انواع مختلفی از عناصر پردازشی باشند. امکان اضافه کردن عناصر پردازشی اضافه‌تری به سیستم وجود دارد. در حالت کلی عناصر پردازشی خودشان یک کامپیوتر کاملی هستند.
مثالی از سیستمهای loosely coupled، Distributed Processing utilities Package است که بعداُ به تفضیل درباره آنها توضیح می‌دهیم.
4- الگوریتمهای موازی (Parallel Algorithm):
یک الگوریتم موازی شامل sub taskهایی است که باید انجام شود. بعضی از این sub taskها بصورت موازی اجرا میشوند، اما گاهی sub taskهایی هم وجود دارد که باید بصورت خطی اجرا شوند. اجرای هر sub task توسط یک پروسس مجزا انجام می‌شود. از ویژگیهای مهم یک الگوریتم موازی نحوه محاوره این پروسسها، سنکرون بودن و قطعی بودن الگوریتم است. دو پروسس با یکدیگر محاوره (interact) دارند، اگر خروجی یکی از آندو پروسس ورودی دیگری باشد. نحوه محاوره دو پروسس می‌تواند بطور کامل مشخص شده باشد یا نباشد. اگر مشخص شده باشد، این دو پروسس فقط زمانی می‌توانند ارتباط داشته باشند که هر دو مایل به انجام ارتباط باشند. اگر گیرنده هنوز آماده ارتباط نباشد، فرستنده نمی‌تواند اقدامی انجام دهد.
در حین اجرای یک الگوریتم سنکرون تمام پروسسها باید قبل از محاوره با یکدیگر همزمان شوند. سنکرون شدن در اینجا یعنی قبل از آغاز subtask جدید، آنها باید منتظر کامل شدن عمل دیگر پروسسها باشند. وقتی یک الگوریتم آسنکرون اجرا می‌شود، پروسسها لازم نیست که منتظر یکدیگر شوند تا taskهایشان را تمام کنند. البته این امکان وجود دارد که یک الگوریتم آسنکرون تا حدی سنکرون شود.
یک الگوریتم قطعی است اگر هر بار که الگوریتم بر روی ورودی مشابه اجرا شود، نتیجه اجرا یکسان باشد. یعنی دستورالعملهای مشابه به ترتیب مشابه انجام شود. بنابراین اجراهای متوالی از یک الگوریتم همیشه خروجی یکسان دارد در حالیکه در الگوریتمهای غیر قطعی یک تصمیم یکسان خروجیهای متفاوتی دارد. مثلاً خروجی یک تصمیم ممکن است و البته به فاکتورهای محیطی معینی باشد که توسط الگوریتم کنترل نمی‌شود. از اینرو اجراهای پی‌در پی یک الگوریتم غیر قطعی، خروجیهای متفاوت تولید می‌کند.
دانلود فایل آشنایی با چند سخت افزار کامپیوتر
| دسته بندی | کامپیوتر و IT |
| بازدید ها | 4 |
| فرمت فایل | doc |
| حجم فایل | 262 کیلو بایت |
| تعداد صفحات فایل | 55 |
آشنایی با چند سخت افزار کامپیوتر
چکیده
امروزه کامپیوتر در موارد متعددی به خدمت گرفته می شود . برخی از تجهیزات موجود در منازل ، دارای نوعی خاصی از ریز پردازنده می باشند . حتی اتومبیل های جدید نیز دارای نوعی کامپیوتر خاص می باشند . کامپیوترهای شخصی ، اولین تصویر از انواع کامپیوترهائی است که در ذهن هر شخص نقش پیدا می کند. که به شرح چند نمونه از سخت افزار کامپیوتر می پردازیم.
1- حافظة RAM (Random Access Memory)
RAM نوعی حافظه است که کامپیوتر از آن برای ذخیره برنامه ها و داده ها هنگام پردازش استفاده می کند. اطلاعات اکثر انواع RAMها هنگام خاموش کردن کامپیوتر پاک می شود. در حال حاضر شرکت ها در تلاش هستند RAMهایی تولید کنند که با خاموش شدن کامپیوترهم، داده ها را در خود نگه دارند (با استفاده از نانوتیوبهای کربنی و اثر تونل های مغناطیسی).
امروزه بعضی از انواع RAMها قادرند اشتباهات تصادفی را تصحیح کنند. در سال های اخیر chipهایی ساخته شده است که تا GB10 حافظه دارند، همینطور chipهایی که اندازه آن ها در حدود 18/0 میکرون می باشد .
انواع RAM (نرخهای عملکرد با رنگ سبز نشان داده شدهاند):
- SDRAM (Synchronous Dynamic RAM) ® 100 MHz
- DDR SDRAM (Double-Data-Rate SDRAM)
- DDR1 (or DDR) ® 100-200 MHz
- DDR2 ® 200-400 MHz
- DDR3 ® 400-800 MHz
- RDRAM (Rambus Dynamic RAM) ® 300-800 MHz
2- Modem
3- دیسک سخت
4- Cpu
فصل اول : حافظه RAM
حافظهRAM (Random Access Memory) شناخته ترین نوع حافظه در دنیای کامپیوتر است . روش دستیابی به این نوع از حافظه ها تصادفی است . چون می توان به هر سلول حافظه مستقیما" دستیابی پیدا کرد . در مقابل حافظه های RAM ، حافظه هایSAM (Serial Access Memory) وجود دارند. حافظه های SAM اطلاعات را در مجموعه ای از سلول های حافظه ذخیره و صرفا" امکان دستیابی به آنها بصورت ترتیبی وجود خواهد داشت. ( نظیر نوار کاست ) در صورتیکه داده مورد نظر در محل جاری نباشد هر یک از سلول های حافظه به ترتیب بررسی شده تا داده مورد نظر پیدا گردد. حافظه های SAM در مواردیکه پردازش داده ها الزاما" بصورت ترتیبی خواهد بود مفید می باشند ( نظیر حافظه موجود بر روی کارت های گرافیک ). داده های ذخیره شده در حافظه RAM با هر اولویت دلخواه قابل دستیابی خواهند بود.
مبانی حافظه های RAM
حافظه RAM ، یک تراشه مدار مجتمع (IC) بوده که از میلیون ها ترانزیستور و خازن تشکیل شده است .در اغلب حافظه ها با استفاده و بکارگیری یک خازن و یک ترانزیستور می توان یک سلول را ایجاد کرد. سلول فوق قادر به نگهداری یک بیت داده خواهد بود. خازن اطلاعات مربوط به بیت را که یک و یا صفر است ، در خود نگهداری خواهد کرد.عملکرد ترانزیستور مشابه یک سوییچ بوده که امکان کنترل مدارات موجود بر روی تراشه حافظه را بمنظور خواندن مقدار ذخیره شده در خازن و یا تغییر وضعیت مربوط به آن ، فراهم می نماید.خازن مشابه یک ظرف ( سطل) بوده که قادر به نگهداری الکترون ها است . بمنظور ذخیره سازی مقدار" یک" در حافظه، ظرف فوق می بایست از الکترونها پر گردد. برای ذخیره سازی مقدار صفر، می بایست ظرف فوق خالی گردد.مسئله مهم در رابطه با خازن، نشت اطلاعات است ( وجود سوراخ در ظرف ) بدین ترتیب پس از گذشت چندین میلی ثانیه یک ظرف مملو از الکترون تخلیه می گردد. بنابراین بمنظور اینکه حافظه بصورت پویا اطلاعات خود را نگهداری نماید ، می بایست پردازنده و یا " کنترل کننده حافظه " قبل از تخلیه شدن خازن، مکلف به شارژ مجدد آن بمنظور نگهداری مقدار "یک" باشند.بدین منظور کنترل کننده حافظه اطلاعات حافظه را خوانده و مجددا" اطلاعات را بازنویسی می نماید.عملیات فوق (Refresh)، هزاران مرتبه در یک ثانیه تکرار خواهد شد.علت نامگذاری DRAM بدین دلیل است که این نوع حافظه ها مجبور به بازخوانی اطلاعات بصورت پویا خواهند بود. فرآیند تکراری " بازخوانی / بازنویسی اطلاعات" در این نوع حافظه ها باعث می شود که زمان تلف و سرعت حافظه کند گردد.
سلول های حافظه بر روی یک تراشه سیلیکون و بصورت آرائه ای مشتمل از ستون ها ( خطوط بیت ) و سطرها ( خطوط کلمات) تشکیل می گردند. نقطه تلاقی یک سطر و ستون بیانگر آدرس سلول حافظه است .
حافظه های DRAM با ارسال یک شارژ به ستون مورد نظر باعث فعال شدن ترانزیستور در هر بیت ستون، خواهند شد.در زمان نوشتن خطوط سطر شامل وضعیتی خواهند شد که خازن می بایست به آن وضغیت تبدیل گردد. در زمان خواندن Sense-amplifier ، سطح شارژ موجود در خازن را اندازه گیری می نماید. در صورتیکه سطح فوق بیش از پنجاه درصد باشد مقدار "یک" خوانده شده و در غیراینصورت مقدار "صفر" خوانده خواهد شد. مدت زمان انجام عملیات فوق بسیار کوتاه بوده و بر حسب نانوثانیه ( یک میلیاردم ثانیه ) اندازه گیری می گردد. تراشه حافظه ای که دارای سرعت 70 نانوثانیه است ، 70 نانو ثانیه طول خواهد کشید تا عملیات خواندن و بازنویسی هر سلول را انجام دهد.
سلول های حافظه در صورتیکه از روش هائی بمنظور اخذ اطلاعات موجود در سلول ها استفاده ننمایند، بتنهائی فاقد ارزش خواهند بود. بنابراین لازم است سلول های حافظه دارای یک زیرساخت کامل حمایتی از مدارات خاص دیگر باشند.مدارات فوق عملیات زیر را انجام خواهند داد :
-- مشخص نمودن هر سطر و ستون (انتخاب آدرس سطر و انتخاب آدرس ستون)
-- نگهداری وضعیت بازخوانی و باز نویسی داده ها ( شمارنده )
-- خواندن و برگرداندن سیگنال از یک سلول ( Sense amplifier)
-- اعلام خبر به یک سلول که می بایست شارژ گردد و یا ضرورتی به شارژ وجود ندارد ( Write enable)
سایر عملیات مربوط به "کنترل کننده حافظه" شامل مواردی نظیر : مشخص نمودن نوع سرعت ، میزان حافظه و بررسی خطاء است .
حافظه های SRAM دارای یک تکنولوژی کاملا" متفاوت می باشند. در این نوع از حافظه ها از فلیپ فلاپ برای ذخیره سازی هر بیت حافظه استفاده می گردد. یک فلیپ فلاپ برای یک سلول حافظه، از چهار تا شش ترانزیستور استفاده می کند . حافظه های SRAM نیازمند بازخوانی / بازنویسی اطلاعات نخواهند بود، بنابراین سرعت این نوع از حافظه ها بمراتب از حافظه های DRAM بیشتر است .با توجه به اینکه حافظه های SRAM از بخش های متعددی تشکیل می گردد، فضای استفاده شده آنها بر روی یک تراشه بمراتب بیشتر از یک سلول حافظه از نوع DRAM خواهد بود. در چنین مواردی میزان حافظه بر روی یک تراشه کاهش پیدا کرده و همین امر می تواند باعث افزایش قیمت این نوع از حافظه ها گردد. بنابراین حافظه های SRAM سریع و گران و حافظه های DRAM ارزان و کند می باشند . با توجه به موضوع فوق ، از حافظه های SRAM بمنظور افزایش سرعت پردازنده ( استفاده از (Cacheو از حافظه های DRAM برای فضای حافظه RAM در کامپیوتر استفاده می گردد.
دانلود فایل مقایسه چهار طرح ضرب کننده RNS
| دسته بندی | کامپیوتر و IT |
| بازدید ها | 10 |
| فرمت فایل | doc |
| حجم فایل | 972 کیلو بایت |
| تعداد صفحات فایل | 130 |
مقایسه چهار طرح ضرب کننده RNS
چکیده
هدف از این پروژه مقایسه چهارطرح ضرب کننده RNS می باشد. بدین منظور با بهره گیری از پیاده سازی این چهار طرح با نرم افزار VHDL به مقایسه آنها می‌پردازیم. RNS یک روش نمایش اعداد است که در آن هر عدد به وسیله باقی مانده‌های تقسیم آن بر مجموعه ای از اعداد دو به دو نسبت به هم اول نمایش داده
می شود. با کمک قضیه باقی مانده چینی، اثبات می شود که در RNS نمایش هر عدد منحصر به فرد می باشد برای ضرب در RNS نیاز به ضرب پیمانه ای خواهد بود. روشهای ضرب پیمانه ای برحسب اینکه کاهش به پیمانه، در کدام مرحله ضرب انجام گیرد. به دو دسته «کاهش در حین ضرب (RDM)» و «کاهش بعد از ضرب (RAM)» تقسیم می شوند. دو طرح اول این پروژه با تکنیک RAM و دو طرح دوم با تکنیک RDM کار می‌کنند.
فهرست مطالب
عنوان صفحه
1- مقدمه.......................................................................................................... 1
1-1 سیستم عددی باقیمانده....................................................................... 1
1-2 قضیه باقی مانده های چینی................................................................ 2
1-3 کاربردهای RNS............................................................... 3
2- روشهای ضرب پیمانه ای .......................................................................... 5
2-1 روش مونتگمری................................................................................ 5
2-2 بررسی اجمالی روشهای موجود پیاده سازی ضرب در RNS............ 6
2-3 نکاتی پیرامون چهار طرح مورد نظر................................................... 7
3- طرح اول..................................................................................................... 8
3-1 مقدمه................................................................................................. 8
3-2 بررسی سوابق..................................................................................... 8
3-3 الگوریتم.............................................................................................. 9
3-4 پیاده سازی سخت افزاری................................................................... 10
3-5 محاسبه پیچیدگی مساحت و تأخیر طرح اول..................................... 13
4- طرح دوم..................................................................................................... 15
4-1 مقدمه................................................................................................. 15
4-2 بررسی سوابق .................................................................................... 15
4-3 الگوریتم.............................................................................................. 15
4-4 پیاده سازی سخت افزاری................................................................... 18
4-5 محاسبه پیچیدگی مساحت و تأخیر طرح دوم..................................... 20
5- طرح سوم.................................................................................................... 21
5-1 تبدیل سیستم RNS (Residue Conversion)................................ 28
5-2 پیاده سازی سخت افزاری................................................................... 30
5-2-1 پیاده سازی تبدیل RNS........................................................... 31
5-2-2 پیاده سازی بخش اصلی الگوریتم (الگوریتم مونتگمری با RNS).. 34
5-3- محاسبه پیچیدگی مساحت و تأخیر طرح سوم ................................ 36
5-3-1 عناصر وابسته به ROM............................................................ 36
5-3-2 عناصر ریاضی........................................................................... 36
5-3-3 تأخیر و مساحت تبدیل کننده RNS استاندارد.......................... 37
5-3-4 محاسبه مساحت و تأخیر تبدیل کننده RNS سریع................... 44
5-3-5 مساحت و تأخیر طرح سوم....................................................... 50
5-4 نتایج پیاده سازی در طرح سوم ......................................................... 56
6- طرح چهارم................................................................................................ 58
6-1 بیان مقاله در مورد سیستم RNS ............................................ 59
6-2 بیان مقاله از ضرب پیمانه ای بدون تقسیم (روش مونتگمری)............ 60
6-3 بررسی صحت الگوریتم...................................................................... 62
6-4 روش تبدیل RNS............................................................................. 66
6-5 پیاده سازی سخت افزاری................................................................... 67
6-5-1 تبدیل RNS ناقص................................................................... 68
6-5-2 پیاده سازی بخش اصلی طرح چهارم (الگوریتم مونتگمری)..... 68
6-6 محاسبه پیچیدگی تأخیر و مساحت طرح چهارم................................ 70
6-6-1 محاسبه تأخیر و مساحت تبدیل RNSناقص............................. 70
6-6-2 محاسبه تأخیر و مساحت در طرح چهارم.................................. 72
6-7 نتایج شبیه سازی در طرج چهارم....................................................... 80
7- مقایسه طرح ها وجمع بندی ..................................................................... 81
7-1- مقایسه چهار طرح............................................................................ 81
7-2- جمع بندی ...................................................................................... 98
8- مراجع.........................................................................................................
9- ضمائم ........................................................................................................
الف – کدهای VHDL طرح اول...............................................................
ب – کدهای VHDL طرح دوم................................................................
ج – کدهای VHDL طرح سوم................................................................
د – کدهای VHDL طرح چهارم..............................................................
هـ – MOMA .........................................................................................