چندین تکنیک دیگر برای اصلاح ساختار درختان CSA معرفی شده است که از کنتورهای 302 برای رسیدن به طرح منظم تر و Lass arebconsuming استفاده می کند.
چنین ساختارهای درختی اصلاح شده ممکن است مستلزم تعداد بیشتری از سطوح CSA با تأخیر کلی بیشتر باشد.
دو نمونه از این فنون بعداً تشریح می شود.
نمونه اول، درختان تأخیر موازنه شده [24] ( همچنین با 19 رجوع شود) را تعیین می کند در حالیکه نمونه دوم، درختان پلکان واژگون را تعیین می کند [15] .
شکل 13- 6 ساختار bit – slices را برای دو تکنیک نشان می دهد و آنها را با Wallace tree bit8slice متناظر مقایسه می کند.
تمام bit – slices در شکل 13- 6 برای 18 operands است که ممکن است بوسیله الگوریتم بزرگ مضاربه ای پایه تولید شود.
در این مورد، 18 مثلث واژگون در شکل 13-6 3و 2 هستند و اعداد روی این کنتورها، تأخیر تجربه شده توسط operands داده را نشان می دهند.
بنابر این ع پس از اینکه نتایج 2~ 64 توسط Wallae و درختان پلکان واژگون تولید شدند، درخت متوازن مستلزم ~ AFA است.
توجه کنید که تمام 3 ساختار درختی ، شامل 15 Carries حاصل بیرون رونده و 15 حاصل وارده شونده هستند و هر حامل بیرون رونده در مسیر حامل وارد شونده خود قرار دارد، برای اینکه با bit – slices مجاور ، متصل شود.
حاملان وارد شونده با کنتورهای مختلف (3 و 29 ronted درگیر می شوند، برای اینکه تمام داده ها به یک کنتور قبل یا در زمان لازم معتبر هستند .
تنها برای درختان متوازن تمام 15 حامل وارد شوندهه هنگامی که لازم هستند به طور کامل تولید می شوند چون تمام مسیرها متوازن هستند در 2 درخت دیگر، کنتورهایی وجود دارد که تمام حاملان وارد شوند به طور همزمان تولید نشوند.
برای مثال، منتور پایینی در درخت پلکان واژگون ، حاملان وارد شونده ای دارد که تأخیرهای مرتبط،44 و54 هستند.
3 ساختار درختی همچنین در تعداد مسیر کشی لازم بین bit – slices مجاور متفاوت هستند، این در عوض بر مساخت طرح اثر می گذارد.
درخت Wallae مستلزم 6 مسیر سیم کشی است، پلکان واژگون و درخت متوازن به ترتیب مستلزم 3 و 2 مسیر هستند.
به رابطه trabeoff لاینفک بین اندازه و سرعت توجه فرمائید.
درخت Wallae، پائین ترین تأخیر کلی را تضمین می کند اما بیشترین تعداد مسیرهای سیم کشی است.
درخت متوازن، از سوی دیگر، مستلزم کمترین تعداد مسیر سیم کشی است اما بیشترین تأخیر کلی را دارد.
درختان متوازن و پلکان واژگون ساختار منظمی دارند و می توانند به روش قانونمندی طراحی شوند این به سختی از شکل 13- 6 دیده می شود، اما از شکل 13- 6 که ساختار کامل دو درخت را مانند آن درخت Wallae متناظر نشان می دهد می توان نتیجه گیری کرد.
آجرهای ساختمان درختان متوازن و پلکان واژگون، با خطوط منظم و برخی انحرافات آنها می توانند از 1241 و [15] مشخص شوند.
در هنگام تعیین طرح نهایی یک درخت SCA، باید دقت شود تا اطمینان حاصل شود که سیم ها، داده ها را به Carry – Save adder با طولی تقریباً مشابه وصل می کنند، در غیر اینصورت مسیرهای متوازن تأخیر دیگر متوازن نخواهند بود.
برای مثال ، یک درخت CSA را برای 27 محصول operands بدست آمده از bit – 53 افزاینده با استفاده از الگوریتم اصلاح شده پایه Booth 4، یک درخت CSA از کمپرسورهای 2 و 4 نشان داده شده در شکل 15- 6 ساخته می شود و طرح متناظر در شکل 15 – 6 (ب) 1251 نشان داده شده است.
توجه کنید که کمپرسور پائینی (13# در وسط قرار دارد، برای اینکه کمپرسورهای 11# و 12# در فاصله نسبتاً مشابهی از آن هستند.
کمپرسور 11# در عوض سیم هایی با طول مشابه از 8# و 9# و ...
دارد.)
• 5 - 6 واحد افزودن مضرب ترکیبی (FMA)
یک واحد FMA، ضرب A * B زیر را فوراً بوسیله یک محصول اضافی و operand سوم (C) انجام می دهد برای اینکه محاسبه A * b + C یک عمل واحد و منفرد انجام می گیرد.
واضح است که چنین واحدی قادر به انجام ضرب تنها با قرار دادن C=0 و جمع (یا تفریق) تنها با قرار دادن برای مثال B=1 می باشد.
یک واحد FMA، ضرب A * B زیر را فوراً بوسیله یک محصول اضافی و operand سوم (C) انجام می دهد برای اینکه محاسبه A * b + C یک عمل واحد و منفرد انجام می گیرد.
واضح است که چنین واحدی قادر به انجام ضرب تنها با قرار دادن C=0 و جمع (یا تفریق) تنها با قرار دادن برای مثال B=1 می باشد.
یک واحد FMA می تواند زمان کلی استخراج ضرب زنجیره ای 0 را کاهش دهد وسپس عملیات تفریق را اضافه نماید.
یک مثال برای این مورد زمانی که این ضرب و جمع زنجیره ای مفیدند، در ارزیابی چند اسمی an * n + a , -1 * n-1 + … + aa از طریق {(GX + an -1) X + an -2} X + … است.
از سوی دیگر ، ضرب مستقل و عملیات جمع نمی توانند به موازات هم انجام گیرند.
مزیت دیگر یک واحد FMA در مقایسه با افزاینده و جمع کننده مجزا، زمان اجرای عملیات نقطه شناور است، چون گرد کردن تنها یکبار برای نتیجه A * B + C انجام می گیرید نه دوبار (ضرب وسپس برای جمع).
چون گرد کردن ممکن است خطا های محاسبه را نشان دهد، کاهش تعداد گرد کردن ها ممکن است اثر مثبتی بر خطای کلی داشته باشد.
در طرح گزارش شده در 1141، این صحت اضافی زمانی مفید بود که به طور صحیحی خارج قسمت را در تقسیم بر الگوریتم متناوب گرد کند.
(رجوع شود به بخش 2 – 8).
شکل 16- 6 اجرای یک واحد FMA را برای محاسبات نقطه شناور نشان می دهد.
در اینجا C , B , A قابل توجه هستند در حالیکهE c ,Eg , Eaبه ترکیب نمونه های operands هستند درخت CSA تمام محصولات نسبی را تولید می کند و جمع آوری Carry – Save را برای تولید 2 نتیجه ای که سپس با operand مرتب شده C به طور صحیح جمع می شود.
جمع کننده 3 operands را می پذیرد و بنابر این، ابتدا باید آنها را به 2 (با استفاده از کنتورهای 2 و 3) کاهش دهد و سپس افزایش حمل – تکثیر را انجام می دهد.
مراحل طرح و نرمال سازی و گرد کردن سپس انجام می گیرند.
طرح نشان داده شده در شکل 16- 6 ، 2 تکنیک را برای کاهش زمان اجرای کلی بکار می برد.
ابتدا، مدار مهم پیش بینی کننده صفر، از تکثیر استفاده می کند و علائم تولید شده توسط adder را برای پیش بینی نوع تغییری که در مرحله پس از نرمال سازی مورد نیاز است، تولید کند.
این مدار به موازات خود جمع عمل می کند برای اینکه تأخیر مرحله نرمال سازی کوتاه تر است.
ثانیاًو مهمتر اینکه ، مرتب کردن C برجسته در Ea + Eg – Ec به موازات ضرب A و B انجام می گیرد.
به طور معمول، یک جمع نقطه شناور، ما اهمیت operand کوچک تر را مرتب می کنیم.
این دلالت دارد بر اینکه اگر محصول AXBکوچکتر از C باشد.
باید محصول را پس از تولید، تغییر دهیم و تأخیر اضافی را نشان دهیم.
ترجیح می دهیم همیشه C را مرتب کنیم حتی اگر بزرگتر از AXB باشد، تا تغییر به موازات ضرب باشد.
برای رسیدن به این ، باید اجازه دهیم که C به راست یا چپ تغییر کند (مسیری که به ترتیب با مثبت یا منفی بودن نتیجه Ea + EB – Ec دیکته می شود).
اگر اجازه بدهیم C به چپ تغییر کند باید عدد کلی Bits در adder افزایش یابد.
برای مثال ، اگر تمام operands، اعداد نقطه شناور در قالب طولانی IEEE هستند، ترتیب ممکن C در رابطه با محصول AXB به صورت زیر نشان داده می شود.
این ترتیب برای 53 – 2 EA + EB – EC 2 53 است.
اگر 54 2 EA + Eg – EC باشد، بیت های C بیشتر به راست تغییر کرده اند، جایگزین بیت چسبنده می شود و اگر 54-5 EA + ED – EC باشد تمام بیت های A * B جایگزین یک بیت چسبنده می گردند.
بنابر این penaity جریمه کلیع 50 درصد افزایش در پهنای adder می باشد که در عوض، زمان اجرای adder را افزایش خواهد داد.
به هر حال توجه کنید که 53 بیت بالای adderتنها لازم است قادر به افزایش محتویات اصلی 53 بیت باشد (اگر یک Carry از106 بیت پائینی تکثیر یابد).
مسیر از محصول مدار گردشی در شکل 16 – 6 به مضرب در سمت راست زمانی بکار می رود که محاسبه ای نظیر (xy + z) + AXB انجام می شود.
مسیر از محصول مدار نرمال سازی به مضرب سمت چپ زمانی بکار می رود که محاسباه ای نظیر (X * Y + Z) + C انجام می شود.
در این مورد مرحله گرد کردن برای (A * B + C) در زمانی مشابه با ضرب در D با افزودن محصول نسبی 1nn * D به درخت CSA انجام می گیرد.
6 – 6 تنظیم مضرب ها در عمل اساسی (تولید محصولات نسبی و جمع) ممکن است ظاهر شوند.
در این روش، از افراطب overhead که بخاطر کنترل های جداگانه این دو عمل است جلوگیری می کنیم و بنابر این سرعت ضرب را بالا می بریم.
این مضرب ها که شامل سلولهای یکسانی است که قارد به تشکیل یک محصول نسبی جدید و افزودن آن به محصول نسبی جمع شده از قبل می باشد، مضرب های کناری نامیده می شوند.
واضح است که هر سودی در سرعت، به هزینه سخت افزار اضافی بدست می آید.
ویژگی مهم دیگر تنظیم مضرب ها این است که آنها می توانند برای حمایت سرعت بالای لوله کشی بکار روند.
برای نشان دادن عمل تنظیم یک مضرب، متوازی الاضلاع 5 * 5 نشان داده شده در شکل 17- 6 را آزمایش می کنیم که شامل 25 بیت محصول نسبی به شکل a4 .
xjاست که به طور صحیحی مرتب شده است.
یک استنباط مستقیم از تنظیم مضرب، دو محصول نسبی نخست را پس از تنظیم صحیح جمع می کند.
نتایج ردیف اول سپس با ad .xz به صورت aD .xz ...
و 22 در ردیف دوم جمع می شود و ....
سلول اصلی برای هر تنظیم مضرب، یک FA مورد قبول یکی از محصولات نسبی جدید (ai .
xi) ، یک بیت از محصول نسبی از قبل جمع شده و یک carry – in – bit است.
یک نمودار block از یک تنظیم 5*5 برای اعداد بدون علامت، در شکل 18 – 6 ترسیم شده است.
در 4 ردیف اول ، هیچ تکثیر افقی carry وجود ندارد.
به عبارت دیگر، یک نوع افزایش carry – save در این ردیف ها انجام می گیرد و محصول سبی جمع شده شامل جمع متوسط و بیت های carry است.
تنها در ردیف آخر ، تکثیر افقی carry مجاز است.
ردیف آخر سلولها در شکل یک ripple carry – adder است که می تواند با یک two – operand adder سریع جایگزین شود (اگر زمان اجرای کلی مطلوب باشد) تنظیم مضرب در شکل 16 – 6 باید برای ضرب اعداد علامت دار در دو تکمیل عدد نویسی اصلاح شود، چون بیت های محصولی نظیر a4 .xo و ao .
x4 ، وزن منفی دارند و باید کسر شوند نهجمع .
یک روش برای کنترل صحیح 8 بیت محصول نسبی وزن شده منفی در یک ضرب 5*5 بیتی، در شکل 19- 6 ترسیم شده است.
بیت ها با وزن منفی.
با یک دایره کوچک به جای یک فلش، نشان داده می شوند.
این بیت ها باید بجای جمع ، کسر شوند.
سلولهای با3 محصول مثبت معمولاً FAS هستند و در شکل با I نشان داده می شوند.
سلولهای با یک داده منفی واحد و دو داده مثبت ، با II نشان داده می شوند.
مجموع 3 داده از یک سلول نوع II می تواند از 1- تا 2 متغیر باشد.
این مستلزم این است که محصول دیجیتالی C ، وزنی معادل با 2+ داشته باشد و محصول عمودی S وزن 1- داشته باشد.
عمل جبری یک سلول نوع II به وسیله معادله با تمام داده های منفی نشان داده شده با I در شکل 23- 6 تشریح می شود و به طور منفی وزن C و محصولات S را می گیرد.
این سلول اعداد1- را در داده هایش می شمرد و این عد را از طریق محصولات C و S نشان می دهد.
عمل منطقی آن مانند سلول نوع I است و بنابر این، اجراهای gate ورودی آنها یکسان است.
این ، تشریح کننده دلیل علامت گذاری آنها به صورت I , I است .
همچنین اجراهای ورودی سلولهای نوع II و II یکسان هستند.
شیوه دیگر برای طرح یک ضرب منظم برای 2 مؤلفه operands، استفاده از الگوریتم Booth است.
یک مضرب طبق این الگوریتم شامل n ردیف از سلولهای اصلی است که n ، تعداد بیت های مضرب است.
هر ردیف قارد به جمع یا کسر مضربهای مرتب شده صحیح به محصول نسبی جمع شده قبلی است.
سلولها در ردیف C ، جمع یا کسر یا تنها تبدیل را بسته به تعداد xi و بیت مرجع مناسب انجام می دهند.
این مضرب در شکل 20 – 6 برای operands 4 بیت داده شده است.
سلول اصلی در این مضربع یک مدار کنترل شده جمع / کسر / تبدیل است که در شکل 20 - 6 الف) ترسیم شده است [12] .
علامت های D , H علامت های کنترل نشان دهنده نوع عمل برای اجرا توسط ردیف متناظر سلولهای CASS است.
اگر H ، صفر باشد هیچ جبری انجام نمی گیرد و بنابر این بیت محصول نسبی جدید که توسط Pwt نشان داده شده است برابر با بیت قبلی است.
اگر H=1 باشد یک عمل جبری انجام گرفته است (تولید یک pwt جدید).
نوع عمل جبری بوسیله علامت D نشان داده می شود.
اگر D=0 باشد، آنوقت بیت مضروب که توسط a نشان داده می شود، به pin با Q اضافه می شود که به عنوان یک بیت حمل وارد شونده از سلول مجاور به سمت راست است.
سپس سلول، pont و C و t را به عنوان حمل خارج شونده به سلول بعدی در سمت چپ تولید می کند.
اگر D=1 باشد ، آنوقت بیت مضرب (a) از pin با Q کم می شود که به عنوان یک borrow وام خارج شونده است.
بنابر این معادلات قانونی برای c , t , t , p چنین است [12] : pat = pin @ (a.H) @ (Q,.H) و Cat = (oin @ D) .
(attim) + A .
Gin .
شیوه ای دیگر برای طرح یک سلول CASS به صورت ترکیب یک mul tiplexer و یک FA است.
علائم کنترل D , H برای ردیف L بوسیله یک مدار CTRL بر اساس بیت مضرب xi و بیت مرجع xi – 1 بدنبال قانون الگوریتم Booth از جدول 1- 6 تولید می شوند.
ردیف اول متناظر است با عمده ترین بیت مضرب.
از اینرو ، محصول نسبی حاصل لازم است قبل از جمع با آن (یا کسر از آن) به سمت چپ تغییر کند.
برای رسیدن به این ، یک سلول جدید با داده pi=0 به ردیف دوم و هر ردیف بعدی اضافه می شود.
چون تعدادبیت ها در محصول نسبی (تا یکی در هر ردیف) افزایش می یابد، لازم است قبل از افزودن یا (کسر آن) به محصول نسبی، مضرب را افزایش دهیم.
این با برگشت بیت علامت مضرب انجام می گیرد.
(شکل 20 – 6 ب).
توجه کنید که نمی توانیم مزیت سیم های D,S یا I , S را در این اجرا داشته باشیم، چون نمی توانیم ردیف ها را حذف کنیم یا جا بزنیم .
بنابر این تنها مزیت این اجرا توانایی ضرب اعداد منفی در دو اجرا است بدون هیچ نیازی به اصلاح مرحله.
همچنین توجه کنید که عمل ردیف i لازم نیست تا زمانیکه ردیف های بالایی عمل خود را تکمیل کنندع به تأخیر بیافتند.
بنابر این آخرین بیت عمده محصول (Po) پس از یک تأخیر سلولCASS تولید خواهد شد، PI پس از 2 تأخیر سلول CASS تولید خواهد شد و مهمترین بیت P2 , -2 پس از 1- n2 تأخیر سلول CASS تولید می شود.
به همین روش می توانیم طرحهای ضرب پایه بالاتر را که مستلزم ردیف های کمتری در آرایه است با بکار گرفتن برای مثال الگوریتم های پایه 4 نشان داده شده در جدول های 3- 6 و 5 – 6 یا الگوریتم مشابه پایه 8 اجرا کنیم.
اینجا همچنین می توانند مضرب های منفی را در دو تصویر تکمیلی کنترل کنند.
آجر ساختمان این مضرب ها یک مدار ضرب کننده – جمع کننده است که مضرب صحیح مضروب A را انتخاب می کند و آنرا با محصول نسبی از قبل جمع شده، جمع می کند تا یک محصول نسبی جمع شده جدید بدست آید.
یک ویژگی مهم مضربهای منظم این است که آنها یک حالت لوله کشی عمل را در جایی که اجرای ضرب جداگانه، o~rlaps است مجاز می سازند.
اگر این عملیات مطلوب باشد، تأخیر طولانی همراه با افزایش تکثیر Carry انجام گرفته در ردیف آخر آرایه (شکل 18 – 6) باید کاهش یابد، چون میزان عملکرد لوله کشی را تعیین می کند.
این می تواند با جایگزین کردن CPA با چند ردیف اضافی بدست آید که مانند ردیف های اول در آرایه ، تکثیر Carry را تنها در یک موقعیت بین هر دو ردیف متوالی مجاز می سازد.
5 تا از این ردیف ها در مضرب منظم 5*5 برای اعداد بدون علامت در شکل 18 – 6 به ترتیب با سلولهای 4، 4، 3، 2، 1 لازم است.
این ردیف ها در یک نسخه لوله کشی شده مضرب منظم 5*5 ترسیم شده در شکل 22 – 6 نشان داده شده اند.
سلولهای اصلی بکار رفته در این مضرب در شکل 21 – 6 نشان داده شده اند.
FA در شکل 21 – 6 شامل یک ورودی AND است که بیت محصول aixi را تولید می کند.
این ببیت محصول به بیت های وارد شونده d , b اضافه می شوند تا بیت های محصول cmt , s را تولید کنند.
FA اصلاح شده نیزه بیت های xi , ai را برای سلولهای مجاور تکثیر می کند.
دو نسخه HA در همان شکل، در 5 ردیف پائین بکار می رود که سلولها فقط 2 بیت محصول را هر یک اضافه می کنند.
برای حمایت لوله کشی، تمام سلول ها در آرایه باید شامل قفل ها باشند، برای اینکه هر ردیف بتواند یک جفت مضروب – مضرب جداگانه را کنترل کند.
ثبت ها نیز برای تکثیر بیت های مضرب به مقصدشان و تکثیر بیت های معمولی که تکمیل شده اند، مورد نیاز می باشند که به موازات تولید بیت های محصول جدید انجام می گیرد.
تا 10 ضرب پی در پی می تواند به طور همزمان در ضرب ترسیم شده در شکل 22- 6 انجام گیرد.
حداکثر میزانی که اعمال ضرب می توانند تکمیل شوند، توسط تأخیر همراه با FA اصلاح شده تعیین می شود که شامل Latches قفلها نیز هست.
این میزان ممکن است در عمل ، برای استفاده به عنوان میزان سرعت مدار، خیلی بالا باشد.
به هر حال، اجراهای دیگر مضرب لوله کشی 5*5 با میزان کمتری، امکان پذیر هستند.
برای مثال ، ردیف ها می توانند برای تشکیل یک مرحله لوله کشی واحد با سرعت پایین تر اما با قفلهای کمتر ترکیب شوند.
7 – 7 بهینه سازی اجراهای مضرب محدودیت های اجرای الگوریتم ها برای ضرب استنتاج شده به روشی مشابه با محدودیت ها برای افزایشی که در بخش 4- 5 تشریح شد، می باشد.
جالب است اشاره کنیم که محدودیت های فرضی برای ضرب، مشابه با محدودیت ها برای جمع است، اگر چه در عمل ، ضرب وقتگیر تر از جمع است.
بنابر این فرض شده را که تمام مدارها را با استفاده از ورودیه ای (f,r) تکمیل می نماید، بپذیریم زمان اجرای یک مدارضرب برای دو operands با n بیت هر یک باید مطلوب باشد.
همچنین اگر سیستم عدد باقیمانده بکار رود، هر چه مدارها کوچکتر باشد، داده های کمتری لازم است و در نتیجه محدودیت کمتری در جایی که m عدد اعدادی است که برای معرفی بزرگترین قدر مطلق در سیستم عدد باقی مانده که در فصل 11 تشریح شد، مورد نیاز است و معمولاً m وقتی بدنبال اجرایی بهینه از یک مضرب در سیستم قرار دادی عدد دو تایی هستید، لازم است زمان اجرا و هزینه های اجرای الگوریتم هایی را که قبلاً برای ضرب شرح دادیم ، مقایسه کنیم.
وقتی زمان اجرا و هزینه اجرا لازم است بحساب آیند یک تابع هدف نظیر A – T می تواند در جایی که A دلالت دارد بر مساحت و T دلالت دارد بر زمان اجرا، بکار رود، شکل کلی تر یک تابع هدف ، A .
TQ است که می تواند کوچکتر یا بزرگتر از یک باشد.
در پایین ، چند مضرب را که بخی در بخش قبل ارائه شده اند مقایسه می کنیم .
مضرب منظم ساده ای که در شکل 18 – 6 ترسیم شده است ساختار بسیار منظمی دارد.
آن می تواند به راحتی به صورت یک آرایه مستطیل شکل بدون اتلاف خرده منطقه تکمیل شود.
سپس آخرین بیت های عمده محصول نهایی در سمت راست مستطیل تولید می شوند در حالیکه مهمترین بیت های محصول ، محصولات ردیف پائین مستطیل هستند که یک CPA را تشکیل می دهند.
اگر چه این اجرا خیلی منظم است و طرح آن بسیار ساده است، اما 2 مانع عمده را مطرح می کند.
اول اینکه آن مستلزم مساحت بسیار زیادی است (متناسب با 2n ) چون شامل abo nz FAS و ورودیه ای AND است.
دوم اینکه زمان اجرای طولانی دارد (حدود 2n) .
دقیق تر اینکه T شامل (n-1) AFA برای ردیف های اول (n-1) و (n-1)AFA اضافی برای CPA است (اگر به صورت ripple – carry – adder نشان داده شده در شکل 18 –6 اجرا شود.) بنابر این یک تابع هدف از شکل A-T تناسب مستقیم دارد با n3 اگر یک نسخه لوله کشی شدید از این مضرب منظم مطلوب باشد.
مساحت مورد نیاز حتی بیشتر از پوشیدگی یک عمل ضرب واحد می شود.
به هر حال لوله کشی حاصل به طور خلاصه سرعت لوله کشی را تعیین می کند.
یک اجرای ضرب منظم الگوریتم Booth که در شکل 20 -6 ترسیم شده است.
زمانی که اجرا و مساحت مورد توجه قرار دارند.
هیچ مزیتی بر مضرب قبلی ندارد.
چون مساحت A طبق n2 است و T در n خطی است.
الگوریتم اصلاح شده 4 پایه Booth (جدول 3-6) می تواند به طور بالوه به اجرایی بهتر بیانجامد چون تنها مستلزم n/2 ردیف سلول است.
این کاهش در تعداد ردیف ها در اصل می تواند تأخیر (T) و هزینه اجرا (A) را به وسیله عامل 2 با کاهش تابع هدف AT به یک چهارم مقدار قبلی اش، کاهش دهد.
بهر حال آزمایش دقیقتر طرح آشکار می سازد که تأخیر واقعی و سودهای مساحت کمتر از انتظار هستند.
قانون ثبت و مهمتر از آن انتخاب گرهای محصول نسبی پیچیدگی را به مدار می افزاید و به عدد بزرگتر ارتباطات درونی و تأخیر طولانی تر در هر ردیف می انجامد.
همچنین چون تغییر نسبی بین هر دو ردیف مجاور، 2 موقعیت بیت است، ما باید اجازه دهیم که carry به صورت افقی در این موقعیت های بیت تکثیر یابد .
این می تواند به صورت محلی یا در ردیف آخر مضرب منظم بدست آید.
پس از آن تکثیر یک carry از طریق (1- n2) بیت (به جای n-1) مورد نیاز است (18) کاهش کلی دقیق در تابع هدف وابسته به جزئیات طرح و تکنولوژی بکار رفته است.
مشکلات مشابه در زمان اجرای الگوریتم اصلاح شده پایه 8 Booth به شکل یک مضرب منظم آشکار می تواند .
بعلاوه محصول نسبی 3A باید از پیش محاسبه شود.
در نتیجه کاهش در تأخیر و مساحت ممکن است خیلی کمتر از عامل مورد انتظار 113 باشد.
هنوز اجرای الگوریتم پایه 4 ممکن است در تکنولوژی های خاص و رئوش های طرح از لحاظ هزینه مؤثر باشد.
صرف نظر از روش تولید محصولات نسبی آنها می توانند از طریق ارتباط درونی یک پوشش یا از طریق یک ساختار درختی تولید شوند.
تعداد سطوح در یک درخت CSA برای محصولات نسبی K طبق Log –k است و خطی بودن در K به زمان اجرای کوتاهتر نمی انجاممد به هر حال ساختارهای درختی CSA ارتباطات درونی نا منظمی دارد که یافتن یک طرح مؤثر مساحت با یک قالب مستطیلی را مشکل می سازد.
بعلاوه یک پهنای کلی 2n در اکثر موارد مورد نیاز است.
این ممکن است به یک مساحت مضربی 2n Log K بیانجامد تابع هدف A.T ممکن است در نتیجه به 2n Lodz k افزایش یابد.
درخت تأخیر متوازن در شکل 13- 6 ساختار منظم تری دارد.
افزایش در تعداد operands در درخت تأخیر متوازن 3، 3، 5، 7، 9، ...
است .
مجموع عناصر در این مجموعه ها به صورت jz است.
تعداد سطوح که تأخیر o~rall را تعین می کند با j به صورت خطی افزایش می یابد.
در نتیجه تأخیر کلی یک درخت تأخیر متوازن 6 است که k=jz تعداد operands است.
اثبات دقیق به عهده خوانندگان است (به عنوان تمرین) شخص باید آگاه باشد که اصطلاحات کلی برای پیچیدگی رمان اجرا یا مساحت نظیر موارد بالا ، اهمیت فرضی دارد اما اهمیت عملی محدود است.
برای هر تکنولوژی ارائه شده آزمایش دقیق تری از طرحهای دیگر قبل از ترسیم نتایج نهایی لازم است.
8-6 تمرینها 6 نشان دهید که الگوریتم Booth می تواند برای تغییر تعددا دو تصویر تکمیلی به تصویر SD بکار رود.
6 ثابت کنید که هیچ مرحله اصلاحی برای زمانی که از الگوریتم ضرب در جدول 3- 6 با یک مضرب منفی در دو تکمیل استفاده می شود لازم نیست اینرا برای الگوریتم در جدول 5-6 با یک علامت افزایش بیت تکرار کنید.
6 اثبات کنید که محصول نسبی جدید در الگوریتم پایه 4 Booth، (22- xi - ?
و xi - است.
A برای مقادیر زوج i از این اصطلاح برای اثبات رسمی اصلاح الگوریتم استفاده کنید.
4-6 قوانین را برای یک الگوریتم اصلاح شده پایه ای booth بنویسید به عبارت دیگر یک نسخه 3 بیتی الگوریتم در جدول 3-6 را بنویسید.
5-6 الف) chip خرده 74261 را اثبات کنید که یک 2 بیتی نامیده می شود (با استفاده از مضرب موازی cbit که الگوریتم را در جدول 3- 6 تکمیل می کند).
ب) چند نمونه از این خرده ها لازم است تا یک بیت 12 *12 دو مضرب تکمیلی ساخته شود؟
نشان دهید که چگونه این خرده ها باید ارتباط درونی داشته باشند؟
ج) توضیح دهید چگونه علائم محصول خرده 74261 برای تولید بیت علامت محصول نسبی بکار می روند.
د9 چه نوع carry – save – adder لازم است؟
6-6 در مورد 101 جدول 6-6 ما به 2 carries اجباری به adder نیاز داریم.
برای جلوگیری از این ممکن است xo را به d تغییر دهیم (اگر آن مساوی با 1 باشد و محصول نسبی ابتدایی را به جای –A و +A قرار دهیم).
نشان دهید که محصول نسبی صحیح همیشه به دست می آید.
6-7 یک مضرب 3n*3n بیتی را از مضرب های n*n بیتی طراحی کنید.
ابتدا تعدا مضرب های n*n بیتی لازم است و نشان دهید که چگونه محصولات باید مرتب شوند چه نوع کنتورهایی برای افزوودن محصولات نسبی مورد نیاز هستند؟
آیا کنتورهای 4 و 5 و 5 می توانند مفید باشند؟
8-6 جدول درستی یک سلول نوع II را در 2 مضرب منظم تکمیلی بنویسید و معادلات Boolean را برای محصولات s , c بدست آورید اینرا برای سلولهای نوع IIتکرار کنید.
9-6 آیا 4 سلول در ردیف آخر در شکل 19- 6 می توانند به نوع II تبدیل شود.
10 – 6 عقیده پشت مضرب منظم در شکل 19 – 6 ابتدا توسط Pezarisطرح شد [19] چه کسی یک سازمان مضرب کمی متفاوت را بصورتی که در شکل 23 – 6 ترسیم شده است، نشان داد.
توضیح دهید چرا محصول p4 در شکل 23 -6 با سلول در سمت چپش مرتبط است.
11-6 یک مضرب منظم برای دو operands دوتایی منفی برای مثال xE1 = zi(-2) طرح کنید دامنه هر operand و محصول چیست؟
مضرب xth =e را ترسیم کنید نشان دهید چند نوع dijterentاز سلولهای یک بیتی مورد نیاز است و جدول درستی را برای هر یک ارئه دهید.
12- 6 در این معادله از شما می خواهیم زمان اجرای یک مضرب منظم را نظیر آنچه در شکل 18-6 است تخمین بزنید .
با A ,A تاخیرهای همرا با مجموع و محصولات carry سلولهای اصلی را نشان دهید و فرض کنید که آنها مطلوبA>A هستند .
مسیر مهم را در مضرب منظم با فرض اینکه تمام محصول ajzj به طور همزمان موجود است بیابید زمان اجرای یک ضرب??
را تخمین بزنید.