عنوان پایان‌نامه
استفاده از پیش بینی ارتباطات برای افزایش کارایی برنامه های موازی
- رشته تحصیلی
- مهندسی کامپیوتر-معماری کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 3062;کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 3062;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77993;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77993
- تاریخ دفاع
- ۲۴ شهریور ۱۳۹۵
- دانشجو
- محمد عظیمی
- استاد راهنما
- مهدی مدرسی
- چکیده
- کاهش اندازه‌ی ترانزیستورها در طی سال‌های اخیر، منجر به افزایش تعداد هسته‌های پردازشی در چندپردازنده‌های روی تراشه شده است. این افزایش تعداد هسته‌ها از سوی دیگر، منجر به بالا رفتن حجم ارتباطات و توان مصرفی شده است. با توجه به این مهم، کاهش توان مصرفی و تأخیر شبکه‌های روی تراشه نقش به سزایی در آینده این صنعت و توانایی بالا بردن تعداد پردازنده‌ها در سیستم‌هایی با تعداد پردازنده بالا دارد. این موضوع به‌اندازه‌ای مهم و حیاتی شده است که سایر روش‌های ارتباطی سنتی، به دلیل عدم مقیاس‌پذیری مناسب و هزینه پیاده‌سازی بالا، جایی در طراحی‌های امروزی ندارد. به همین منظور شبکه‌های روی تراشه ، به‌عنوان یک راه‌حل مقیاس‌پذیر و مناسب برای استفاده در سیستم‌های روی تراشه معرفی شدند. دو پارامتر مهم و تأثیرگذار در طراحی، تأخیر و توان مصرفی می‌باشند. اغلب طراحی‌های شبکه‌های روی تراشه مبتنی بر راه‌گزینی بسته است تا بتوان از قابلیت گذردهی و مقیاس‌پذیری بالای آن استفاده کرد. این روش با وجود این مزیت‌ها، مشکلاتی نیز به همراه دارد. یکی از مهم‌ترین آن‌ها سربار توان مصرفی و تأخیر مسیریاب‌ها است که مانعی برای عملکرد بهینه و مطلوب این روش شده‌اند. دلیل اصلی سربار تأخیر و توان مصرفی این روش، نیاز به تخصیص منابع و ذخیره‌سازی داده‌ها به‌صورت گام‌به‌گام است. برای کاستن این سربارها، می‌توان منابع را پیش از نیاز در اختیار بسته قرار داد تا تخصیص منابع به‌صورت گام‌به‌گام، از مسیر بحرانی بسته خارج گردد. این روش که تخصیص زودهنگام نامیده می‌شود، می‌تواند قسمت اعظمی از سربار توان ناشی از ذخیره‌سازی گام‌به‌گام را کاسته و تأخیر را بهبود بخشد. اغلب روش‌های موجود با ایده‌ی تخصیص زودهنگام، در معماری حافظه‌ی مشترک اعمال‌شده و شبکه‌های ارسال پیام ، با داشتن بستر بسیار مناسب برای بهره جستن از این قابلیت مورد توجه قرار نگرفته‌اند. با توجه به این مطلب، هدف از این پایان‌نامه، توسعه‌ی ایده‌ی تخصیص زودهنگام در شبکه‌های ارسال پیام است. با استفاده از این روش، تخصیص منابع در هر مسیریاب از چند واحد زمانی پیش از رسیدن داده، انجام می‌گردد. در پیاده‌سازی روش پیشنهادی، امکان تخصیص زودهنگام برای تمامی حالات وجود ندارد و از راه‌گزینی بسته به‌عنوان مکمل استفاده شده است. پس روش پیشنهادی را می‌توان روشی ترکیبی در نظر گرفت که مبتنی بر راه‌گزینی بسته و راه‌گزینی مدار است. برای تخصیص منابع، شبکه‌ای بسیار سبک در کنار شبکه‌ی داده طراحی شده که وظیفه‌ی آن ارسال پیام کنترلی، جهت تخصیص زودهنگام منابع مسیریاب برای داده‌ی موردنظر است. ارزیابی نتایج حاصل از شبیه‌سازی‌ها، حاکی از این است که این روش می‌تواند مقیاس‌پذیری بالای راه‌گزینی بسته را با کارایی بالای راه‌گزینی مدار ترکیب کرده و تأخیر ناشی از عبور بسته‌های داده در شبکه و همچنین توان مصرفی را به ترتیب 45 و 11 درصد کاهش دهد.
- Abstract
- Message passing programing model is a more scalable alternative to the shared memory model for parallel machines. Parallel programming models are generally categorized by how memory space is distributed. In the shared memory model, all processes share the same address space. However, in the message passing model, an application runs as a collection of autonomous processes, each with its own local memory and private address space. In the message passing model, processes communicate with other processes by explicitly sending and receiving messages that transfer the data from the local memory of one to the local memory of the other. In general, message passing is more scalable and hence, is used in large parallel computers with distributed memory, such as clusters of servers and supercomputers. Conventional chip multiprocessors with less than ten cores use the shared memory model. However, as the core count increases, the message passing model becomes more popular due to its better scalability. In addition, multicore system-on-chip (SoC) designs, in which the application is explicitly divided by programmer into several parallel tasks, best fit the message passing model. Prior research shows that parallel programs lose a considerable amount of potential performance due to the long latency inter-task communication. A common network-on-chip (NOC) in today's many-core processors is a two-dimensional mesh. The performance in mesh-based NoCs is mainly affected by average hop count, each hop involving a router traversal. Most of the router delay is due to resource allocation: on arriving to a router, a packet needs to select its output port and then allocate crossbar input and output ports of the router and free virtual channel and buffer slot at the downstream router. Then, it uses the allocated resources to go to the next hop. To reduce per-hop delay, prior work proposed allocating the resources to a packet a few cycles before its arrival to a router. While these methods work in shared memory parallel machines, in this thesis, we propose to use proactive NoC resource allocation for message passing programs. In this method, by inserting a customized primitive, called Pre-SEND(), before a SEND() primitive a path between the source and destination of the SEND() primitive is set up in advance. Pre-SEND() primitives increase the performance of SEND() primitives in the same way as the prefetch instructions (that are included in almost all modern ISAs) facilitate data access for load instructions in a processor. This method relies on a low bit-width control network to handle Pre-SEND() primitives and convert them to setup messages that proactively select route and reserve switch passage and buffer for their corresponding data packets. Once a path is pre-established (either partially or fully), the packet traverses the path in the ideal one hop per cycle speed, as it do not need to go through routing, arbitration, and VC allocation at each hop. It simply traverses the crossbar switches and links that cover the physical distance between the two end-point nodes of the connection. Since the speed of data packets is faster than setup messages, it is very likely that a data packet reaches its corresponding setup message. In this case, the setup message is discarded and data packet continues the rest of the path by packet-switching. By proactive path setup, data packets are not needed to get buffered and hence, the power overhead of buffering (that accounts for a considerable portion of router power consumption) is saved. Experimental results on several parallel programs show that this method can respectivly reduce the power consumption and latency of routers by 45% and 11%.
