دسته بندی | کامپیوتر و IT |
بازدید ها | 26 |
فرمت فایل | 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 |
بازدید ها | 12 |
فرمت فایل | doc |
حجم فایل | 262 کیلو بایت |
تعداد صفحات فایل | 55 |
آشنایی با چند سخت افزار کامپیوتر
چکیده
امروزه کامپیوتر در موارد متعددی به خدمت گرفته می شود . برخی از تجهیزات موجود در منازل ، دارای نوعی خاصی از ریز پردازنده می باشند . حتی اتومبیل های جدید نیز دارای نوعی کامپیوتر خاص می باشند . کامپیوترهای شخصی ، اولین تصویر از انواع کامپیوترهائی است که در ذهن هر شخص نقش پیدا می کند. که به شرح چند نمونه از سخت افزار کامپیوتر می پردازیم.
RAM نوعی حافظه است که کامپیوتر از آن برای ذخیره برنامه ها و داده ها هنگام پردازش استفاده می کند. اطلاعات اکثر انواع RAMها هنگام خاموش کردن کامپیوتر پاک می شود. در حال حاضر شرکت ها در تلاش هستند RAMهایی تولید کنند که با خاموش شدن کامپیوترهم، داده ها را در خود نگه دارند (با استفاده از نانوتیوبهای کربنی و اثر تونل های مغناطیسی).
امروزه بعضی از انواع RAMها قادرند اشتباهات تصادفی را تصحیح کنند. در سال های اخیر chipهایی ساخته شده است که تا GB10 حافظه دارند، همینطور chipهایی که اندازه آن ها در حدود 18/0 میکرون می باشد .
انواع RAM (نرخهای عملکرد با رنگ سبز نشان داده شدهاند):
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 در کامپیوتر استفاده می گردد.
دسته بندی | کامپیوتر و IT |
بازدید ها | 10 |
فرمت فایل | doc |
حجم فایل | 3531 کیلو بایت |
تعداد صفحات فایل | 16 |
حافظة مجازی
حافظه مجازی
در این تمرین شما با صورتها و شکلهای مختلفی از مکانیزم حافظه مجازی در ویندوز NT آشنایی پیدا خواهید کرد علیرغم اغلب دیگر سیستمهای عامل، ویندوز NT یک API ساده و روشنی را برای اداره کردن بعضی شکلها و صورتهای حافظه مجازی تهیه میکند(معمولاً حافظه مجازی بطور کامل توسط برنامه نویس کاربردیاش روشن و واضح میگردد) در این تمرین شما در موارد زیر اطلاعاتی یاد خواهید گرفت: سازماندهی سیستم حافظه مجازی ویندوز NT چگونه فضای حافظه مجازی خود را کنترل کنید؟ چگونه یک وسیله آگاه کننده و گزارش دهنده بنویسید؟ جزئیات GlobalMemory Status , GetsystemInfo – VirtualQuery – VirtualUnlock – VirtualLock – VirtueaFree – VirtualAlloc معرفی
حافظه مجازی صفحهبندی یا Paging Virtual Memory در بسیاری از سیستمهای عامل امروزی بکار گرفته میشود. در یک سیستم صفحهبندی شده، هر فرآیندی یک فضای آدرس دهی مجازی خاص خود دارد که برای ارجاع دیگر اشیاء بکار گرفته میشود که معمولاً محتوای یک محل یا موقعیتی از حافظه است بخشی از فضای آدرس دهی مجازی توسط ویراستار خطی ( Link editor ) تعریف میشوند وقتی که آن یک تصویر قابل اجرایی بوجود میآورد که در واقع فایل اجرایی یا EXE است. تعداد باقیمانده از فضای آدرسدهی میتواند بطور پویا در زمان اجرا توسط روشهایی که در این تمرین توضیح داده خواهد شد تعر یف شود. بعد از اینکه قسمت پایدار و ثابت از فضای آدرسدهی مجازی ایجاد شد در حافظه ثانویه ذخیره خواهد شد ( معمولاً در بخش یا Partition از وسیله ذخیرهسازی کهPaging disk نام دارد ). به منظور عملیتر شدن شما میتوانید Paging disk را مشابه فایل در نظر بگیرید. در یک کامپیوتر معمول و مرسوم پردازنده تنها میتواند دستورات را واکشی کند یا دادههایی را که در حافظه اولیه یا قابل اجرا ( که معمولاً RAM خوانده میشوند. ) واقع شدهاند را بارگذاری کند. حافظه اولیه در مقایسه با حافظه ثانویه کوچکتر و سریعتر است. حافظه اولیه خیلی گرانتر از حافظه ثانویه است بنابراین بطور معمول در زمره اجزای با ارزشتر از نظر حجم اما کوچکتر از حافظههای ثانویه قرار دارند. اغلب کامپیوترها حافظه اولیه کافی حتی برای ذخیره فضای آدرسدهی مجازی کامل یک فرآیند را هم ندارند بنابراین در یک زمان تعداد زیادی فضا روی حافظه ثانویه برای ذخیره فضای آدرسدهی مجازی تعداد زیادی فرآیند وجود خواهد داشت. حافظه اولیه همچنین خیلی سریعتر از حافظه ثانویه میباشد. پردازنده میتواند یک بایت را در 2 سیکل پردازنده در حافظه اولیه بخواند یا بنویسید. اما همین عمل هزاران سیکل از پروسسور را برای نوشتن یا خواندن اطلاعات در حافظه ثانویه نیازمند است.برای نگهداری فضای حافظه اولیه یک سیستم حافظه مجازی صفحهبندی شده در هر زمان داده شده تنها بخشی از فضای آدرسدهی مجازی تعداد مختلفی از فرآیندها را بارگذاری یا ( Load ) میکند. همانطور که Thread ها در فضای آدرسدهی فرآیندهایشان اجرا میشوندبخشی از فضای آدرسدهی مجازی که در حال حاضر در حال استفاده است در حافظه اولیه بارگذاری میشود و در همان حال دیگر بخشهای فضای آدرسدهی در حافظه ثانویه قرار گرفتهاند. زمانی که فرآیندی به بخشی از فضای آدرسدهی مجازی دیگر نیاز ندارد ( حداقل برای مدتی ) از آن بخش در حافظه ثانویه کپی گرفته میشود. این به موقعیتی از حافظه اولیه که مورد استفاده برای ذخیره بخشی از فضای آدرسدهی مجازی قرار گرفته بود این اجازه را میدهد که برای ذخیره بخش دیگری از فضای آدرسدهی مجازی در زمان دیگری بکار گرفته شود. در یک سیستم حافظه مجازی سنجش در کارایی بوسیله کپی کردن یک بلوک از حافظه در حافظه اولیه یا بازگرداندن به حافظه ثانویه در زمانی که یک جابهجایی بین دوسطح از سلسله مرتبه حافظ مورد نیاز و ضروری باشد بدست میآید کارایی از این واقعیت بدست میآید که عملیات ورودی و خروجی حافظه ثانویه وابسته به بلوکها میباشد. این یعنی اگر تنها یک کلمه ( Word ) اطلاعات از حافظه ثانویه مورد نیاز باشد همه بلوک باید خوانده شود تابه آن کلمه برسیم. همچنین نسبت به مکانی که همه آن بلوک در حافظه اولیه قرار داد هم احساس است تا زمانی که باید خوانده شود تابه لغت گم شده برسیم. فواید دیگری در بارگذاری همه بلوکها نسبت به فقط یک کلمه وجود دارد. هنگامی که یک نخ یا Thread به مکانی چون I رجوع میکند احتمال زیادی وجود دارد که بخواهد به مکان I+1 در آینده نزدیک رجوع کند به این مفهوم محلیت یا Locality گفته میشود. یک حافظه مجازی صفحهبندی شده بلوکهای با اندازة ثابت را بارگذاری میکند و یا برمیدارد که به آنها صفحه یا Page گفته میشود که در زمانی که دادهها و اطلاعات را بین حافظه اولیه و ثانویه در جهت رفت و برگشت حرکت میدهد انجام میگیرد. حد و مرز صفحهها یا Page ها کاملاً توسط برنامهنویس مشخص و واضح میشود. شکل 1 عملیات یک سیستم حافظه مجازی صفحهبندی شده بطور عام را خلاصه میکند.زمانی که یک نخ یا Thread به آدرس مجازی K رجوع میکند ( مرحله 1 در شکل ) حافظه مجازی ابتدا تعدا صفحات یا Page هایی که آدرس مجازی K را در بردارد تعیین میکند (مرحله2 در شکل ) اگر صفحه در حال حاضر در حافظه اولیه بارگذاری شده بود و موجود بود ( مرحله 3 در شکل ) سیستم حافظه مجازی آدرس مجازی را به آدرس فیزیکی متناظر با آن موقعیت در حافظه اولیه که همان Page Frame است تبدیل میکند ( جایی که صفحه هدف در آن واقع شده است. ) اگر صفحه در همان زمان که به آن رجوع شده بارگذاری نشده بود اجرای Thread عادی دچار وقفه میشود تا زمانی که مدیریت حافظه صفحه مقصد را در Page Frame بارگذاری کند به محضی که آن صفحه بارگذاری شد اجرا ادامه پیدا خواهد کرد در مرحله 4 رجوع به آدرس مجازی K دوباره با آدرس فیزیکی در حافظه اولیه تعیین میگردد ( مکانی که موقعیت مجازی K در حال حاضر آنجا بارگذاری شده است. )
حافظه مجازیدر این تمرین شما با صورتها و شکلهای مختلفی از مکانیزم حافظه مجازی در ویندوز NT آشنایی پیدا خواهید کرد علیرغم اغلب دیگر سیستمهای عامل، ویندوز NT یک API ساده و روشنی را برای اداره کردن بعضی شکلها و صورتهای حافظه مجازی تهیه میکند(معمولاً حافظه مجازی بطور کامل توسط برنامه نویس کاربردیاش روشن و واضح میگردد) در این تمرین شما در موارد زیر اطلاعاتی یاد خواهید گرفت: سازماندهی سیستم حافظه مجازی ویندوز NT چگونه فضای حافظه مجازی خود را کنترل کنید؟ چگونه یک وسیله آگاه کننده و گزارش دهنده بنویسید؟ جزئیات GlobalMemory Status , GetsystemInfo – VirtualQuery – VirtualUnlock – VirtualLock – VirtueaFree – VirtualAlloc معرفی حافظه مجازی صفحهبندی یا Paging Virtual Memory در بسیاری از سیستمهای عامل امروزی بکار گرفته میشود. در یک سیستم صفحهبندی شده، هر فرآیندی یک فضای آدرس دهی مجازی خاص خود دارد که برای ارجاع دیگر اشیاء بکار گرفته میشود که معمولاً محتوای یک محل یا موقعیتی از حافظه است بخشی از فضای آدرس دهی مجازی توسط ویراستار خطی ( Link editor ) تعریف میشوند وقتی که آن یک تصویر قابل اجرایی بوجود میآورد که در واقع فایل اجرایی یا EXE است. تعداد باقیمانده از فضای آدرسدهی میتواند بطور پویا در زمان اجرا توسط روشهایی که در این تمرین توضیح داده خواهد شد تعر یف شود. بعد از اینکه قسمت پایدار و ثابت از فضای آدرسدهی مجازی ایجاد شد در حافظه ثانویه ذخیره خواهد شد ( معمولاً در بخش یا Partition از وسیله ذخیرهسازی کهPaging disk نام دارد ). به منظور عملیتر شدن شما میتوانید Paging disk را مشابه فایل در نظر بگیرید. در یک کامپیوتر معمول و مرسوم پردازنده تنها میتواند دستورات را واکشی کند یا دادههایی را که در حافظه اولیه یا قابل اجرا ( که معمولاً RAM خوانده میشوند. ) واقع شدهاند را بارگذاری کند. حافظه اولیه در مقایسه با حافظه ثانویه کوچکتر و سریعتر است. حافظه اولیه خیلی گرانتر از حافظه ثانویه است بنابراین بطور معمول در زمره اجزای با ارزشتر از نظر حجم اما کوچکتر از حافظههای ثانویه قرار دارند. اغلب کامپیوترها حافظه اولیه کافی حتی برای ذخیره فضای آدرسدهی مجازی کامل یک فرآیند را هم ندارند بنابراین در یک زمان تعداد زیادی فضا روی حافظه ثانویه برای ذخیره فضای آدرسدهی مجازی تعداد زیادی فرآیند وجود خواهد داشت. حافظه اولیه همچنین خیلی سریعتر از حافظه ثانویه میباشد. پردازنده میتواند یک بایت را در 2 سیکل پردازنده در حافظه اولیه بخواند یا بنویسید. اما همین عمل هزاران سیکل از پروسسور را برای نوشتن یا خواندن اطلاعات در حافظه ثانویه نیازمند است.برای نگهداری فضای حافظه اولیه یک سیستم حافظه مجازی صفحهبندی شده در هر زمان داده شده تنها بخشی از فضای آدرسدهی مجازی تعداد مختلفی از فرآیندها را بارگذاری یا ( Load ) میکند. همانطور که Thread ها در فضای آدرسدهی فرآیندهایشان اجرا میشوندبخشی از فضای آدرسدهی مجازی که در حال حاضر در حال استفاده است در حافظه اولیه بارگذاری میشود و در همان حال دیگر بخشهای فضای آدرسدهی در حافظه ثانویه قرار گرفتهاند. زمانی که فرآیندی به بخشی از فضای آدرسدهی مجازی دیگر نیاز ندارد ( حداقل برای مدتی ) از آن بخش در حافظه ثانویه کپی گرفته میشود. این به موقعیتی از حافظه اولیه که مورد استفاده برای ذخیره بخشی از فضای آدرسدهی مجازی قرار گرفته بود این اجازه را میدهد که برای ذخیره بخش دیگری از فضای آدرسدهی مجازی در زمان دیگری بکار گرفته شود. در یک سیستم حافظه مجازی سنجش در کارایی بوسیله کپی کردن یک بلوک از حافظه در حافظه اولیه یا بازگرداندن به حافظه ثانویه در زمانی که یک جابهجایی بین دوسطح از سلسله مرتبه حافظ مورد نیاز و ضروری باشد بدست میآید کارایی از این واقعیت بدست میآید که عملیات ورودی و خروجی حافظه ثانویه وابسته به بلوکها میباشد. این یعنی اگر تنها یک کلمه ( Word ) اطلاعات از حافظه ثانویه مورد نیاز باشد همه بلوک باید خوانده شود تابه آن کلمه برسیم. همچنین نسبت به مکانی که همه آن بلوک در حافظه اولیه قرار داد هم احساس است تا زمانی که باید خوانده شود تابه لغت گم شده برسیم. فواید دیگری در بارگذاری همه بلوکها نسبت به فقط یک کلمه وجود دارد. هنگامی که یک نخ یا Thread به مکانی چون I رجوع میکند احتمال زیادی وجود دارد که بخواهد به مکان I+1 در آینده نزدیک رجوع کند به این مفهوم محلیت یا Locality گفته میشود. یک حافظه مجازی صفحهبندی شده بلوکهای با اندازة ثابت را بارگذاری میکند و یا برمیدارد که به آنها صفحه یا Page گفته میشود که در زمانی که دادهها و اطلاعات را بین حافظه اولیه و ثانویه در جهت رفت و برگشت حرکت میدهد انجام میگیرد. حد و مرز صفحهها یا Page ها کاملاً توسط برنامهنویس مشخص و واضح میشود. شکل 1 عملیات یک سیستم حافظه مجازی صفحهبندی شده بطور عام را خلاصه میکند.زمانی که یک نخ یا Thread به آدرس مجازی K رجوع میکند ( مرحله 1 در شکل ) حافظه مجازی ابتدا تعدا صفحات یا Page هایی که آدرس مجازی K را در بردارد تعیین میکند (مرحله2 در شکل ) اگر صفحه در حال حاضر در حافظه اولیه بارگذاری شده بود و موجود بود ( مرحله 3 در شکل ) سیستم حافظه مجازی آدرس مجازی را به آدرس فیزیکی متناظر با آن موقعیت در حافظه اولیه که همان Page Frame است تبدیل میکند ( جایی که صفحه هدف در آن واقع شده است. ) اگر صفحه در همان زمان که به آن رجوع شده بارگذاری نشده بود اجرای Thread عادی دچار وقفه میشود تا زمانی که مدیریت حافظه صفحه مقصد را در Page Frame بارگذاری کند به محضی که آن صفحه بارگذاری شد اجرا ادامه پیدا خواهد کرد در مرحله 4 رجوع به آدرس مجازی K دوباره با آدرس فیزیکی در حافظه اولیه تعیین میگردد ( مکانی که موقعیت مجازی K در حال حاضر آنجا بارگذاری شده است. )
دسته بندی | کامپیوتر و IT |
بازدید ها | 27 |
فرمت فایل | doc |
حجم فایل | 29 کیلو بایت |
تعداد صفحات فایل | 43 |
سازمان و کار درونی کامپیوترها
درون کامپیوتر
در این بخش مقدمه ای را برای سازمان و کار درونی کامپیوترها فراهم می آوریم. مدل بکار رفته یک مدل عمومی است، ولی مفاهیم مورد استفاده قابل اعمال به همه کامپیوترها از جمله PS/2 , IBM و سازگار با آنهاست. قبل از آغاز این مبحث،مروری بر تعاریف برخی از اصطلاحات در کامپیوتر،مانند کیلو (k) ، مگا،گیگا، بایت، RAM, ROM و غیره مفید است.
بعضی اصطلاحات مهم
یکی از امکانات مهم یک کامپیوتر حافظه موجود در آن است. بنابراین اکنون اصطلاحات بکار رفته برای اندازه حافظه در IBM PC ها و سازگار با آنها را بیان می کنیم. از بحث قبل بیاد دارید که بیت یک رقم دودویی بود که می توانست مقدار 0 یا 1 داشته باشد. بایت یک مجموعه 8 بیتی است. نیبل نصف یک بایت، یا 4 بیت است. کلمه دو بایت یا 16 بیت می باشد. نمایش زیر به منظور نشان دادن اندازه نسبی این واحدها ارائه شده است. البته،آنها می توانند هر ترکیبی از صفرها و یک ها باشند.
یک کیلوبایت، 10 2 بایت یا 1024 بایت است. اغلب از K برای بیان آن استفاده می شود. مثلاً برخی از فلاپی دیسک ها (یا دیسک نرم) k 356 داده را نگه می دارند. یک مگابایت، یا ساده تر مگ، 20 2 بایت است. این مقدار، کمی بیش از یک میلیون بایت است و مقدار دقیق آن 576/048/1 می باشد. با گذری سریع در ظرفیت به گیگابایت یا 30 2 بایت می رسیم (بیش از 1 بیلیون یا میلیارد)، و یک ترابایت نیز 40 2 بایت است (بیش از 1 تریلیون). برای مثالی از چگونگی کاربرد آنها،فرض کنید که کامپیوتری دارای 16 مگابایت حافظه باشد. این مقدار برابر با 220 * 16 یا 220 * 4 2 یا 224 است. بنابراین 16 مگابایت 224 بایت می باشد.
در میکروکامپیوترها معمولا از دو نوع حافظه استفاده می شود که عبارتند از RAM ، که به معنی حافظه با دستیابی تصادفی است (گاهی هم حافظه خواندن / نوشتن نامیده می شود) و ROM که به معنی حافظه فقط خواندنی می باشد. RAM بوسیله کامپیوتر برای ذخیره سازی موقت برنامه های در حال اجرا مورد استفاده قرار می گیرد. این برنامه ها یا اطلاعات بعد از خاموش شدن کامپیوتر از بین می روند. به همین دلیل، RAM را گاهی حافظه فرار هم می خوانند. ROM برای برنامه ها و اطلاعات لازم در عملکرد کامپیوتر لازم است. اطلاعات در ROM دائمی است و قابل تعویض بوسیله کاربر نمی باشد و پس از خاموش شدن کامپیوتر هم از بین نمی رود. بنابراین آن را حافظه غیرفرار گوییم.
سازمان درونی کامپیوترها
بخش عملیاتی هر کامپیوتر قابل تفکیک به سه قسمت است: CPU (واحد پردازش مرکزی)، حافظه و وسایل I/O (ورودی / خروجی) ، شکل 9-0 ملاحظه شود. نقش CPU اجرای (پردازش) اطلاعات ذخیره شده در حافظه است. عمل وسایل I/O همچون صفحه کلید، مانیتور تصویر (ویدئو) ، تهیه مفاهیم ارتباط و محاوره با CPU است. CPU از طریق رشته ای از سیم ها به نام گذرگاه به حافظه و I/O متصل است. گذرگاه داخل یک کامپیوتر، درست مثل گذرگاههای خیابانی که مردم رااز مکانی به مکانی دیگر هدایت می کنند، اطلاعات را از جایی به جای دیگر انتقال می دهند. در هر کامپیوتر سه نوع گذرگاه موجود است: گذرگاه آدرس، گذرگاه داده و گذرگاه کنترل.
به منظور شناسایی یک وسیله (حافظه یا I/O ) توسط CPU ، باید آدرسی به آن تخصیص داد. آدرس اختصاص یافته به یک وسله مورد نظر باید منحصر به فرد باشد؛ یعنی دو وسیله مختلف مجاز به داشتن یک آدرس نیستند. CPU آدرس را روی گذرگاه آدرس قرار می دهد (البته به شکل دودویی) و مدار دیکد وسیله را می یابد. آنگاه CPU از گذرگاه داده برای بدست آوردن داده از وسیله یا ارسال داده به آن استفاده می نماید. گذرگاههای کنترل برای تهیه سیگنال های خواندن و نوشتن در وسیله و مطلع ساختن آن از تصمیم CPU برای دریافت اطلاعات و یا ارسال اطلاعات به آن است. از سه گذرگاه فوق، آدرس و داده، توانمندی یک CPU را نشان می دهند.
توضیحی بیشتر درباره گذرگاه داده
چون گذرگاههای داده برای انتقال اطلاعات به و یا از CPU بکار می روند، هر چه گذرگاههای داده بیشتر باشند، CPU بهتر است. اگر گذرگاههای داده را همچون خطوط اتوبان تصور کنیم، واضح است که هر چه خطوط بیشتر باشند، مسیر بین CPU و وسایل بیرونی (مانند چاپگرها، ROM, RAM و غیره ، شکل 10-0 ملاحظه شود) بهتر خواهد بود. اما افزایش در تعداد خطوط، هزینه ساخت را افزایش می دهد. گذرگاههای حافظه بیشتر،بمعنای CPU و کامپیوتر گرانتر می باشد. اندازه متوسط گذرگاه داده در CPU ها بین 8 و 64 متغیر است، کامپیوترهای اولیه مانند Apple2 از یک گذرگاه داده 8 بیت استفاده می کردند، در حالیکه سوپرکامپیوترهایی همچون Cray گذرگاه داده 64 بیتی را به کار می برند. گذرگاههای داده دو طرفه هستند، زیرا CPU از آنها به هنگام دریافت و یا ارسال داده استفاده می کند. توان پردازش CPU به اندازه این گذرگاهها وابسته است، زیرا یک گذرگاه 8 بیتی هر بار قادر است 1 بایت داده را بفرستد،ولی گذرگاه 16 بیتی، 2 بایت را هر بار ارسال می کند که در نتیجه دو برابر سریعتر خواهد بود.
توضیحی بیشتر درباره گذرگاه آدرس
چون گذرگاه آدرس برای شناسایی وسیله و حافظه متصل به CPU بکار می رود، هر چه گذرگاههای آدرس بیشتر باشند، تعداد وسایلی که آدرس دهی می شوند بیشتر خواهند بود. به بیان دیگر تعداد گذرگاههای آدرس برای یک CPU ، تعداد مکان هایی را که با آن محاوره می کند افزایش می دهد. همواره تعداد مکان ها است که در آن x تعداد خطوط آدرس می باشد و ربطی به اندازه خطوط داده ندارد. مثلا یک CPU با 16 خط آدرس می تواند 65536 (216 ) یا k 64 حافظه را آدرس دهی کند. هر مکان حداکثر 1 بایت داده دارد. به این دلیل است که غالباً تمام ریزپردازنده های همه منظور را بایت آدرس پذیر می نامند. برای مثالی دیگر، کامپیوتر IBM PC AT از یک CPU با 24 خط آدرس و 16 خط داده استفاده می کند. در این حالت،کل حافظه قابل دسترس،16 مگابایت خواهد بود (مگابایت 16=224) در این مثال 224 مکان وجود دارد، و چون هر مکان یک بایت است،16 مگابایت حافظه موجود خواهد بود. گذرگاه آدرس یک گذرگاه یک طرفه می باشد، و به این معنی است که CPU از گذرگاه آدرس فقط برای ارسال آدرس به خارج از خود استفاده می کند. بطور خلاصه: تعداد کل حافظه های آدرسپذیر بوسیله یک CPU همیشه برابر با x2 می باشد که در آن x تعداد بیت های آدرس است و ربطی به اندازه گذرگاه داده ندارد.
CPU و ارتباط آن با RAM و ROM
در پردازش اطلاعات بوسیله CPU ، داده باید در RAM یا ROM ذخیره شود. وظیفه ROM در کامپیوترها ارائه اطلاعات ثابت و دائمی است. این اطلاعات عبارتند از :جداول برای الگوی کاراکترهای مورد نمایش روی صفحه مانیتور، یا برنامه هایی که در کامپیوتر نقش اساسی دارند، مانند برنامه هایی که کل RAM موجود در سیستم را می یابند و یا تست می کنند، و یا برنامه هایی که اطلاعات را روی مانیتور نمایش می دهند. بر عکس، RAM برای ذخیره اطلاعاتی بکار می رود که غیر دائمی و قابل تغییر با زمان می باشند، مانند انواع سیستم های عامل و بسته های کاربردی مثل بسته های پردازش کلمات و محاسبه مالیاتی. این برنامه ها را برای پردازش توسط CPU در RAM قرار داده می شوند. CPU اطلاعات مورد پردازش را از RAM یا ROM دریافت می نماید. در صورتیکه آن را در آنجا نباید شروع به جستجو در وسایل ذخیره سازی حجیم مانند دیسک می نماید، و سپس اطلاعات را به RAM منتقل می کند به این دلیل، گاهی RAM و ROM را حافظه اصلی می نامند و دیسک ها نیز حافظه ثانوی خوانده می شوند.
درون CPU ها
برنامه ذخیره شده در حافظه دستورالعمل هائی را برای CPU فراهم می سازد تا بر اساس آن عملی را انجام دهد. عمل می تواند یک جمع داده ساده همچون صورتحساب و یا کنترل یک ماشین مانند روبات باشد. برداشت این دستورات از حافظه و اجرای آنها بعهده CPU است. برای انجام اعمال برداشت و اجرا، تمام CPU ها مجهز به امکانات زیر هستند:
1- قبل از هر چیز تعدادی ثبات در اختیار CPU قرار دارد. CPU از این ثبات ها برای ذخیره موقت اطلاعات استفاده می کند. اطلاعات می تواند دو مقدار مورد پردازش و یا آدرس مقدار مورد نظری باشد که باید از حافظه برداشت شود. ثبات های درون CPU می توانند 8 بیت ، 16 بیت، 32 بیت و یا حتی 64 بیت باشند. اندازه آنها به CPU بستگی دارد. بطور کلی هر چه ثبات ها بیشتر و بزرگتر باشند، CPU مناسب تر است. عیب ثبات های بیشتر و بزرگتر، گرانی CPU می باشد.
2- CPU دارای بخشی بنام ALU (واحد حساب/ منطق) است. بخش ALU در CPU مسئول انجام اعمال حسابی مانند جمع، تفریق، ضرب و تقسیم، و اعمال منطقی مانند AND ، OR و NOT می باشد.
3- هر CPU دارای یک شمارنده برنامه است. نقش شمارنده برنامه اشارهبه آدرس دستورالعمل بعدی برای اجرا است. با اجرای هر دستورالعمل، شمارنده برنامه افزایش یافته و به آدرس دستورالعمل بعدی برای اجرا اشاره خواهد کرد. در این اشاره، محتوای شمارنده برنامه روی گذرگاه آدرس قرار گرفته و دستورالعمل مورد نظر را یافته و آن را از مبدأ برداشت می کند. در IBM PC شمارنده برنامه را IP یا اشاره گر دستورالعمل می خوانند.
4- نقش دیکدر دستورالعمل ، تفسیر دستور برداشت شده توسط CPU است. می توان دیکدر دستورالعمل را همانند یک فرهنگ لغت تصور کرد که مفهوم هر دستورالعمل را ذخیره نموده و CPU را در برداشت قدم های بعدی پس از دریافت دستورالعمل هدایت می کند. همانطور که فرهنگ لغت باتعریف هر چه بیشتر لغات نیاز به صفحات بیشتری دارد، CPU هم در درک دستورالعمل های بیشتر نیاز به ترانزیستورهای بیشتری خواهد داشت.
عملیات درونی کامپیوتر
برای نمایش برخی از مفاهیم مورد بحث فوق، تحلیل قدم به قدمی از پردازش یک CPU برای جمع سه عدد در زیر داده شده است. فرض کنید که یک CPU فرضی دارای چهارثبات با نام های D,C,B,A باشد. این پردازشگر دارای گذرگاه داده 8 بیتی و گذرگاه آدرس 16 بیتی است. بنابراین CPU می تواند به حافظه هایی از 0000 تا FFFFH دسترسی داشته باشد (جمعاً H 10000 مکان) . عملی که CPU می خواهد انجام دهد عبارتست از قراردادن مقدار 21 در ثبات A و سپس جمع ثبات A با مقادیر H42 و H12 فرض کنید که کد انتقال مقدار به ثبات A برابر (BOH) 10111000 و کد جمع یک مقدار به ثبات A نیز (04H ) 0100 0000 باشد. مراحل لازم و کد اجرای آنها برابر زیر است:
اگر برنامه اجرایی فوق در مکان هایی از حافظه قرار گیرد که از H 1400 شروع می شود. محتوای هر مکان حافظه بقرارزیراست:
عملیاتی که CPU برای اجرای برنامه فوق طی می کند بقرار زیر است:
1- شمارنده برنامه CPU می تواند مقداری بین 0000 و FFFFH داشته باشد. باید 1400 را در شمارنده برنامه نشاند تا آدرس اولین دستورالعمل برای اجرا مشخص گردد. پس از بارکردن شمارنده برنامه با آدرس اولین دستورالعمل، CPU آماده اجرا است.
2- CPU ، H 1400 را روی گذرگاه آدرس قرار داده و آن را به خارج ارسال می دارد. مدار حافظه مکان را می یابد و در این هنگام CPU نیز سیگنال READ را فعال می نماید و به این ترتیب بایت مکان H1400 را از حافظه درخواست می کند. این موجب می شود تا محتوای حافظه در مکان H 1400 ، که B0 است، روی گذرگاه قرار گیرد و به CPU انتقال یابد.
3- CPU دستورالعمل B0 را به کمک مدار دیکد دستورالعمل، دیکد می کند. پس از یافتن تعریف دستورالعمل متوجه می شود که باید محتوی مکان حافظه بعدی را به ثبات A در داخل CPU بیاورد. بنابراین به مدار کنترل خود فرمان اجرای دقیق آن را صادر می نماید. وقتی که مقدار H 21 را از مکان 1401 حافظه به درون آورد، دریچه های ورودی همه ثبات ها را بجز ثبات A ، می بندد. بنابراین مقدار H 21 وقتی وارد CPU شود مستقیماً وارد ثبات A می گردد. پس از تکمیل یک دستورالعمل ، شمارنده برنامه به آدرس دستورالعمل بعدی برای اجرااشاره می کند، که در این حالت 1402 است. سپس آدرس H 1402 به روی گذرگاه آدرس ارسال می شود تا دستورالعمل بعدی برداشت شود.
4- آنگاه از مکان H 1402 ، کد 04 را بر می دارد. پس از دیکد کردن، CPU می فهمد که باید محتوای ثبات A را با بایتی که در آدرس بعدی قرار دارد (1403) جمع کند. پس از آوردن مقدار (در این حالت H42 ) به درون CPU ، مقدار درون ثبات A را همراه با این مقدار به ALU برای انجام جمع تحویل می دهد. سپس نتیجه جمع را از خروجی ALU دریافت کرده و در ثبات A قرار می دهد. در این هنگام شمارنده برنامه برابر با H 1404 ، یعنی آدرس دستورالعمل بعدی می گردد.
5- آدرس H 1404 روی گذرگاه آدرس قرار می گیرد و کد درون آن آدرس به داخل CPU آورده شده و سپس دیکد و اجرا می گردد. مجدداً این کد مقداری را به ثبات A می افزاید. شمارنده برنامه به H 1406 اصلاح می شود.
6- نهایتاً، محتوای آدرس 1406 برداشت و اجرا می گردد. این دستورالعمل، HALT ، به CPU می فهماند تا افزایش شمارنده برنامه را متوقف نماید. در غیاب HALT ، CPU به اصلاح شمارنده برنامه ادامه داده و دستورالعمل ها را برداشت می نماید.
اکنون فرض کنید که آدرس H1403 به جای H 42 ، حاوی 04 باشد. CPU چگونه داده 04 را برای جمع از کد 04 تفکیک می کند؟ بخاطر آورید که برای این CPU ، کد 04 به معنی انتقال یک مقدار به داخل ثبات A است، بنابراین CPU سعی بر دیکد مقدار بعدی نخواهد کرد، بلکه محتوای مکان حافظه بعدی را بدون توجه به مقدار آن بداخل ثبات A منتقل می سازد.
این فصل با بحثی در موردنقش و اهمیت میکروکنترلرها در زندگی روزمره آغاز می شود. در بخش 1-1 روال انتخاب یک میکروکنترلر، همراه با استفاده از آنها را مورد بحث قرار می دهیم. بخش 2-1 انواع اعضای خانواده 8051 ، همچون 8052 ، 8031 و ویژگی های آنها را پوشش می دهد. بعلاوه انواع مختلف 8051 مانند 8751 ، AT 51C89 و 5000DS را مورد بحث قرار خواهیم داد.
دسته بندی | کامپیوتر و IT |
بازدید ها | 26 |
فرمت فایل | doc |
حجم فایل | 972 کیلو بایت |
تعداد صفحات فایل | 130 |
هدف از این پروژه مقایسه چهارطرح ضرب کننده 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 .........................................................................................