We present an algorithm for pipelining loop execution in the presence of loop carried dependences. We optimize both the initiation interval and the turn around time of a schedule. Given constraints on the number of functional units and buses, we 6rst determine an initiation interval and then incrementally partition the operations into blocks to fit into the execution windows. A refinement procedure is incorporated to improve the turn around time. The novel feature which differs our approach from others is that the scheduled operations are iteratively moved up and down to accommodate the ready yet unscheduled operations. The algorithm produces very encourageous results

چکیده

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

1-مقدمه

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