تنظیم مجدد اجرای معامله برای تقویت برنامه های معاملاتی با فرکانس بالا

تجارت با فرکانس بالا (HFT) همیشه مورد استقبال قرار گرفته است زیرا این امر نه تنها از مزایای شخصی بلکه کل رفاه اجتماعی نیز سود می برد. در حالی که پیشروی اخیر انتخاب نمونه کارها در بازار HFT باعث می شود سود بیشتری کسب کند ، اما بار کار OLTP را به همراه دارد. با این حال ، با بهره برداری از موازی سازی فراوان ، خط لوله معامله ، مکانیسم پیشرفته کنترل همزمانی (CC) ، با این حال ، از همزمانی محدودی که با بار کاری HFT روبرو است رنج می برد. انواع آن که با استفاده از اطلاعات مشاجره ریز دانه ، اجرای موازی بیشتری را امکان پذیر می کند نیز تأثیر کمی دارد. برای حل این مشکل ، ما برای اولین بار منبع همزمانی محدود را به عنوان سفارش مضر اظهارات معامله مشاهده و تدوین می کنیم. برای حل و فصل سفارش مضر ، ما PARE را پیشنهاد می کنیم ، یک اجرای مجدد خط لوله ، برای بهبود عملکرد برنامه با تنظیم مجدد اظهارات به ترتیب درجات مشاجره آنها ، عملکرد برنامه را بهبود بخشیم. در بتن ، دو مکانیسم برای اطمینان از صحت بازآرایی بیانیه و شناسایی درجه های مشاجره اظهارات طراحی شده است. ما همچنین مشکل تنظیم مجدد خارج از خط را مطالعه می کنیم. ما ثابت می کنیم که این مشکل NP سخت است و یک رویکرد تنظیم مجدد خارج از خط برای تقریب استراتژی بهینه تنظیم مجدد ارائه می دهد. نتایج آزمایش نشان می دهد که PARE می تواند توان معامله را بهبود بخشد و تأخیر معاملات را در برنامه های HFT تا حداکثر از مکانیسم CC پیشرفته کاهش دهد.

روی نسخه خطی کار می کنید؟

از رایج ترین اشتباهات خودداری کنید و نسخه خطی خود را برای ویراستاران ژورنال آماده کنید.

معرفی

شمارش هسته اصلی CPU و حجم حافظه در حال افزایش ، شاهد رنسانس مکانیسم های کنترل همزمانی (CC) در بهره برداری از موازی فراوان است [24]. خط لوله معامله ، مکانیسم پیشرفته CC ، از مکانیسم های CC قبلی ، از جمله قفل دو فاز (2PL) ، کنترل همزمانی خوش بینانه (OCC) و کنترل همزمانی چند نسخه (MVCC) استفاده می کند ، با اجازه موازی تراعدام در بین عملیات متناقض [16 ، 36]. با این حال ، از تأخیرهای طولانی مدت در مواجهه با برنامه های تجارت با فرکانس بالا (HFT) رنج می برد.

برنامه های HFT از دهه گذشته به بازار جهانی منتقل شده است [1] ، از سرمایه گذاری های فردی مانند مدیریت صندوق های متقابل گرفته تا رفاه اجتماعی ، مانند مدیریت صندوق بازنشستگی [8]. پیشروی اخیر در انتخاب نمونه کارها در بازار HFT باعث ترغیب هر تجارت سیگنال های سرمایه گذاری قوی و ضعیف به دلیل مدیریت ریسک می شود [35]. از آنجا که گرفتن سیگنال های سرمایه گذاری قوی ، مانند انتشار جدید تولید ، آسان تر است ، الگوریتم های مختلف انتخاب نمونه کارها تمایل به دریافت همان سیگنال های سرمایه گذاری قوی دارند در حالی که در سیگنال های سرمایه گذاری ضعیف متفاوت هستند [12]. به عنوان مثال ، لیست 1 معاملات تولید شده توسط دو پرتفوی را توصیف می کند که منعکس کننده همان سیگنال های سرمایه گذاری قوی برای خرید سهام از الفبای امنیتی ، آمازون و توییتر است در حالی که هیچ سیگنال سرمایه گذاری ضعیفی مشترک ندارند. در نتیجه ، بارهای کاری HFT عملیات های زیادی را با مواردی که به ندرت مورد اعتراض قرار می گیرند ، به ترتیب نشان می دهد که به ترتیب سیگنال های سرمایه گذاری قوی و ضعیف را منعکس می کنند.

شکل 1A اجرای دو معاملات در لیست 1 تحت خط لوله پیشرفته مکانیسم CC را نشان می دهد. اولین عملیات متناقض ، به عنوان مثال ، به روزرسانی در مورد الفبای ، ترتیب سریال قابل استفاده از دو معامله را تعیین می کند ، یعنی ، (T_1 ) قبل از (T_2 ) اتفاق می افتد. سپس ، هر عملیاتی در (T_2 ) باید از این دستور پیروی کند. در غیر این صورت ، این عملیات پس از تشخیص تخلف دوباره اجرا می شود. همانطور که شکل 1A نشان می دهد ، این معادل تأخیر در اجرای هرگونه عمل در (T_2 ) تا زمان اتمام عملیات متناقض مربوط به آن در (T_1 ) است. از یک طرف ، این اجازه می دهد تا قبل از اتمام (T_1 ) ، (t_2 ) را انجام دهد. بنابراین ، خط لوله معامله در واقع از همه 2PL ، OCC و MVCC بهتر است ، که اجازه اجرای همپوشانی را نمی دهد زیرا در غیر این صورت بن بست (2PL) یا بازگشت (OCC و MVCC) اتفاق می افتد. از طرف دیگر ، به روزرسانی دوم در (T_2 ) در توییتر باید تا زمان اتمام (T_1 ) به تأخیر بیفتد. در مقایسه با شکل 1B ، که با توجه به لیست 2 ، اجرای (T_1 ) و (T_2 ) را دوباره می بینیم ، می توانیم ببینیم که تأخیر در لیست 1 به طور غیر ضروری باعث افزایش توان می شود و تأخیر معامله را افزایش می دهد.

مقایسه تأخیر بین معاملات اصلی و مرتب شده. خط لوله معامله در معامله اصلی. b خط لوله معامله در معامله مرتب شده

از آنجا که تأخیر عمدتاً در اثر عملیات متناقض ایجاد می شود ، کار زیادی بر استخراج اطلاعات مشاجره ریز و درشت تر از معانی معاملات برای بهره مندی از خط لوله معامله متمرکز است [13 ، 36 ، 41 ، 42]. با این حال ، اطلاعات مشاجره ریز و درشت باعث کاهش مشاجره کاذب می شود ، در حالی که شکل 1A نشان می دهد که برنامه های HFT از این نوع انواع خط لوله معامله سود کمی سود می برند.

به عنوان یک راه حل ، ما در این مقاله PARE ، یک اجرای تنظیم شده از معاملات را ارائه می دهیم. به بهترین دانش ما ، اولین بار است که تنظیم مجدد اجرای معامله به نفع مکانیسم CC خط لوله معامله است. اول ، ما ترتیب مضر بیانیه ها را در کد معامله مشاهده و تدوین می کنیم و پیشنهاد می کنیم با تنظیم مجدد بیانیه ها در کاهش ترتیب درجه مشاجره ، سفارش مضر را از بین ببریم. برای این منظور ، ما دو مکانیسم را ابداع می کنیم. از یک طرف ، برای حفظ سریال سازی پس از تنظیم مجدد ، ما یک الگوریتم استخراج بلوک را تنظیم می کنیم. از طرف دیگر ، برای اندازه گیری میزان مشاجره ، ما یک پیشخوان مبتنی بر اپراتور فیزیکی را ابداع می کنیم.

هنگامی که درخواست های معامله از قبل در دسترس است ، ما یک رویکرد تنظیم مجدد خارج از خط برای بهینه سازی برنامه ریزی معاملات پیشنهاد می کنیم. ما ثابت می کنیم که این مشکل بهینه سازی NP سخت است و یک روش اکتشافی را برای تقریب راه حل بهینه پیشنهاد می کند. ما عملکرد و عملی Pare را ارزیابی می کنیم. نتایج آزمایش نشان می دهد که PARE معامله را در کل بهبود می بخشد و تأخیر معاملات را تا حداکثر بزرگی نسبت به مکانیسم های پیشرفته CC کاهش می دهد. علاوه بر این ، سربار زمان اجرا محدود است.

سهم این مقاله پنج برابر است:

ما اهمیت تنظیم مجدد اجرای معامله را برای خط لوله معاملات پیشرفته مکانیسم CC تحت برنامه های HFT نشان می دهیم.

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

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

ما مشکل تنظیم مجدد خارج از خط را تدوین می کنیم ، اثبات می کنیم که NP سخت است و رویکردی برای تقریب برنامه بهینه تنظیم مجدد ارائه می دهد.

ما آزمایشاتی را برای نشان دادن اثربخشی و عملی PARE انجام می دهیم.

آثار مقدماتی و مرتبط

در این بخش ، ابتدا مکانیسم CC خط لوله معامله را معرفی می کنیم و سپس کار مربوطه را مرور می کنیم. خوانندگان آشنا با خط لوله معاملات می توانند از فرقه عبور کنند. 2. 1

خط لوله معامله

خط لوله معاملات مکانیسم پیشرفته CC است و از موازی سازی بسیار بیشتر از سایر مکانیسم های CC بهره برداری می کند. برای اطمینان از سریال سازی ، مکانیسم های CC قبلی از جمله 2PL ، OCC و MVCC بین معاملات متناقض محدود می شوند [16]. به طور خاص ، اگر معامله (T_2 ) (T_1 ) را بخوانید به X ، همه 2PL ، OCC و MVCC برنامه هایی را تولید می کنند که در آن (t_2 ) خوانده شده همیشه دنبال می شود (t_1 ) تکمیلبشردر زیر 2PL ، هر معامله قفل های طولانی مدت را در سوابق نگه می دارد. هر قفل به دست آمده توسط یک معامله فقط در پایان اجرای آن منتشر می شود [15]. این نظم و انضباط طولانی ، اجرای متضاد را می خواند و می نویسد. اگر معامله (t_2 ) بخواند (t_1 ) بنویسد تا x را ضبط کند ، و (t_1 ) قفل نوشتن را روی x نگه می دارد تا زمانی که کامل شود ، (t_2 ) خوانده شده فقط می تواند پس از پردازش شود.(T_1 ) کامل می شود. تحت OCC ، معاملات انجام می شود در یک بافر محلی می نویسد و فقط پس از اعتبارسنجی ، این نوشته ها را در پایگاه داده فعال کپی می کند [23]. بنابراین ، نوشته های یک معامله فقط در پایان معامله قابل مشاهده است. تحت MVCC ، هر نوشتن هنگام انجام معامله ، با یک جدول زمانی نوشتن اختصاص می یابد و هر خواندن هنگام شروع معامله با یک زمان بندی خوانده شده همراه است. هر خواندن فقط می تواند یک رکورد را بخواند که Timestamp نوشتن آن کمتر از Timestamp خوانده شده باشد [27]. بنابراین ، MVCC به طور مشابه معاملات متناقض را محدود می کند.

برنامه های کاربردی از جمله برنامه های HFT نیاز به همزمانی تهاجمی بیشتری دارند. در نتیجه، خط لوله تراکنش یک انتخاب طراحی جدید از داده های غیرمتعهد عملیاتی را باز می کند. دو مکانیسم برای اطمینان از سریال پذیری اعمال می شود. اولاً، چون داده های غیرمتعهد خوانده می شوند، یک انضباط commit اعمال می شود که (1) اگر تراکنش T بر روی داده های غیرمتعهد از (T') عمل کند و (T') متعهد نشده باشد، T نباید متعهد شود. و (2) اگر (T') سقط شود، T نیز باید سقط شود [16، 36]. ثانیاً، وابستگی هایی که به دلیل تراکنش ها باعث ایجاد دسترسی های متناقض به داده ها می شوند، باید ردیابی شوند و این وابستگی ها باید با محدود کردن دسترسی به داده های بعدی تراکنش اعمال شوند. خط لوله تراکنش تکنیک های زمان اجرا را با تجزیه و تحلیل استاتیک بارهای کاری تراکنش ترکیب می کند. تجزیه و تحلیل استاتیک بر اساس کار قبلی در مورد برش تراکنش است [5، 34]. به طور خاص، یک گراف تضاد ایستا (SC-graph) ایجاد می کند که در آن یک تراکنش به عنوان یک سری قطعات اتمی نشان داده می شود که هر یک به یک یا چند پایگاه داده دسترسی دارند. اگر هر دو به یک جدول دسترسی داشته باشند و یکی از دسترسی ها یک نوشتن باشد، دو قطعه از تراکنش های مختلف به هم متصل می شوند. چرخه ای که شامل چندین قطعه از برخی تراکنش ها است (به عنوان مثال، یک چرخه SC) نشان دهنده نقض احتمالی سریال پذیری است. خط لوله تراکنش از زمان اجرا خود برای محدود کردن اجرای قطعات مربوطه استفاده می کند. برای مثال، اولین باری که (T_2) نوشتن غیرمتعهد (T_1) را می خواند، مشخص می شود که (T_2) باید بعد از (T_1) اتفاق بیفتد. سپس، اگر (T_2) بخواهد y را بنویسد، که (T_1) نیز ممکن است به آن دسترسی داشته باشد، دسترسی (T_2) تا پایان (T_1) به تعویق خواهد افتاد یا دوباره به y دسترسی نخواهد داشت.

کارهای مرتبط

کار ما بر روی خط لوله تراکنش ساخته شده است، و از کد تراکنش بیشتر از خط لوله تراکنش اصلی استفاده می کند.

انواع خط لوله معاملات بیشترین توجه را در تحقیقات کنترل همزمانی به خود جلب می کنند. این روش ها با فرض اینکه بارهای کاری از قبل در دسترس هستند ، نشان می دهد. به این ترتیب ، آنها می توانند معاملات را به صورت قطعاتی خرد کنند به گونه ای که پس از شروع هر قطعه کد معامله ، تا زمان اتمام کل معامله نیازی به تأخیر نخواهد داشت. در رویکرد اصلی خط لوله معامله به نام IC3 [36] ، آیا دو قطعه درگیری بستگی به این دارد که آیا آنها به همان جدول دسترسی پیدا می کنند و یکی از آنها شامل نوشتن است. در صورت انجام دسترسی متناقض در زمان اجرا ، انواع دانه های ریز در رابطه با دو قطعه به عنوان قطعات متضاد ارائه می شود [13 ، 16 ، 41]. به طور خاص ، THEDB [41] عملیات دسترسی به وابستگی ها را ضبط می کند و عضویت در مجموعه های خواندن/نوشتن را توسط داده های غیرقابل قبول از معاملات وابسته آن به روز می کند. هر دو IC3 و THEDB یک نسخه اصلی نسخه را به کار می گیرند. MV3C [13] یک ذخیره سازی چند نسخه را اتخاذ می کند. از آنجا که تنها راه برای ایجاد درگیری این است که یک معامله برخی از اشیاء داده را از پایگاه داده می خواند که تا زمانی که می خواهد مرتکب شود ، بی رنگ می شوند. به این ترتیب ، نوشتن غیر متفاوتی باید در مورد این خواندن ها اعمال شود. برای این منظور ، هر خواندن با بلوک های کدی که به آنها بستگی دارد همراه است. به این ترتیب ، بخشی از معامله ای که باید در این مورد دوباره اجرا شود که داده های غیرمجاز برای خواندن اعمال می شوند به سرعت شناسایی می شوند. PWV [16] داده های غیرقابل قبول را در پایگاه داده تعیین کننده کار می کند. این معاملات را به مجموعه ای از اقدامات فرعی یا قطعات تجزیه می کند به گونه ای که هر قطعه از یک یا چند بیانیه معامله تشکیل شده است. PWV به محض ضمانت معامله میزبان خود ، می نویسد ، حتی اگر هنوز قطعاتی از همان معامله وجود نداشته باشد ، می نویسد.

در بین این روش ها ، IC3 [36] و THEDB [41] بار کار ثابت را در رابط های ساده دریافت/قرار دادن/اسکن فرض می کنند و بنابراین نمی توان در بارهای کاری HFT پویا ، که توسط SQL بیان شده است ، اعمال کرد. MV3C [13] و PWV [16] معاملات را با دست ، که در برنامه های HFT نیز غیر عملی است ، حاشیه نویسی می کنند. در مقابل ، PARE ما به طور خودکار بر روی SQL های تولید شده پویا کار می کند و بنابراین می تواند در معاملات سریع تغییر شده توسط برنامه های HFT اعمال شود. علاوه بر این ، این روش ها دوباره ترتیب اجرای معاملات را در نظر نمی گیرند و بنابراین از عملکرد پایین تحت بار کاری HFT رنج می برند.

تجزیه و تحلیل برنامه به طور گسترده ای برای بهبود عملکرد پایگاه داده از دیدگاه برنامه داده ها اتخاذ شده است. هر دو نوع خط لوله معامله و PARE بر اساس کار قبلی در تجزیه و تحلیل معاملات آماری برای کمک به کنترل همزمانی زمان اجرا ساخته شده اند. از نمودارهای درگیری مدتهاست که برای تجزیه و تحلیل روابط متناقض بین عملیات معامله و حفظ سریال سازی با پیش بینی سفارشات معاملات استفاده می شود [6 ، 7]. با این حال ، کار اولیه با متوقف کردن کلیه معاملات دیگر در یک چرخه ، وابستگی چرخه ای را به خود اختصاص می دهد. کار بیشتر شروع به تجزیه معاملات به قطعات می کند [5 ، 14 ، 18 ، 19 ، 34]. برای حفظ سریال پذیری پس از خرد کردن ، ابتدا مشاهده می شود که اگر همه قطعات رفت و آمد در معامله تجزیه شده ، به راحتی می توان اعدام ها را به هم زد [17]. با این حال ، این یک وضعیت قوی است و بسیاری از بارهای کاری OLTP کافی نیست. علاوه بر این ، نشان داده شده است که در صورت عدم وجود چرخه SC در SC-Graph ، می توان سریال پذیری را حفظ کرد [5]. این تئوری بیشتر به سیستم های توزیع شده گسترش یافته است [9].

تجزیه و تحلیل برنامه همچنین برای استخراج معانی مورد سوء استفاده قرار گرفته است تا اجازه می دهد تا به هم آمیختگی غیرقانونی عملیات پایگاه داده شود. پروتکل مشخص کردن [4] با حفظ یک محدودیت یکپارچگی ، اجرای ناهمزمان معاملات را در یک سیستم تکرار شده فراهم می کند. پروتکل های کنترل واگرایی توزیع شده [31 ، 40] به برخی از ناسازگاری ها اجازه می دهد اما آن را محدود می کند تا اطمینان حاصل شود که برنامه های تولید شده در اپسیلون از سریال سازی قرار دارند [32]. اخیراً ، یک مدل سازگاری مداوم [43] برای خدمات تکثیر شده ارائه شده است که به ناسازگاری محدود می شود و از الگوریتم های ضد انتروپی [28 ، 29] استفاده می کند تا آن را در سطح قابل قبول نگه دارد. اخیراً یک پروتکل هموستاز پیشنهاد شده است. این ویژگی است که محدودیت هایی را که به طور خودکار حفظ می شود ، استنباط می کند [33]. I-Confluence [3] تعیین می کند که آیا یک عملیات متناقض بر اساس معیار صحت وابسته به کاربرد ، متناقض را حفظ می کند. همچنین تحقیقات گسترده ای در مورد شناسایی مواردی وجود دارد که معاملات یا عملیات رفت و آمد می کنند و اجازه می دهند درگیری های غیر قابل قبول و در عین حال صحیح باشد [2 ، 22 ، 25]. متفاوت از این آثار ، PARE اجرای غیرقانونی را ممنوع می کند و بنابراین می تواند بدون دخالت انسان اعمال شود.

از تجزیه و تحلیل برنامه نیز برای سرعت بخشیدن به معاملات استفاده می شود. Sloth [11] و Pyxis [10] ابزاری هستند که از تجزیه و تحلیل برنامه برای کاهش ارتباطات شبکه بین برنامه و DBMS استفاده می کنند. Quo [42] وابستگی های بین بیانیه های معامله را برای اجرای مجدد اجرای معامله برای 2PL دنبال می کند. Dora [30] همچنین کدهای معامله را برای بهره برداری از موازی سازی درون متقابل ارائه شده توسط سرور چند هسته ای برای 2PL تقسیم می کند. اکثر این تکنیک ها در نظر گرفتن مجدد اجرای معامله را در نظر نمی گیرند و بنابراین نمی توانند تأخیر در خط لوله معاملات را کاهش دهند. به نظر می رسد که قرآن بیشترین رویکرد برای PARE از آنجا که هر دوی آنها اجرای معامله را مرتب می کنند. با این حال ، دو انتخاب نامناسب طراحی QUO مانع از خط لوله معاملات از افزایش برنامه های HFT: (1) QUO بار کار ثابت را فرض می کند و نیاز به نمونه گیری از درجه های مشاجره برای هر بیانیه از قبل دارد. متأسفانه ، نمونه گیری بار کار ممنوع است زیرا هر معامله به صورت پویا با توجه به اطلاعات به موقع تجارت در بازار HFT تولید می شود.(2) QURO میزان اختلاف را در سطح بیانیه و با تاخیر در زمان تخمین می زند. همانطور که در فرقه بحث شد. 3. 3 ، این میزان مشاجره را دست کم می گیرد و به طور مکرر میزان مشاجره متناقض را بدست می آورد. در مقابل ، برآورد PARE در سطح اپراتور فیزیکی و فراوانی وقوع مشاجره را شمارش می کند.

اعدام مجدد آگاه خط لوله

در این بخش ، ما ابتدا استراتژی تنظیم مجدد PARE را استنباط می کنیم و سپس دو مکانیسم را برای فعال کردن این استراتژی ارائه می دهیم.

استراتژی تنظیم مجدد

ما مشاهده می کنیم که دو نوع تأخیر در خط لوله معامله وجود دارد که تنها منبع عملکرد فرومایه است. نوع اول تأخیرها از اولین عملیات متناقض ، مانند به روزرسانی (الفبای) معامله (T_2 ) در شکل 1 ناشی می شود. زیرا نوشتن به همان شیء به طور همزمان نامشخص است ، چنین تأخیر اجتناب ناپذیر است. خوشبختانه ، این نوع تأخیرها فقط برای یک عملیات به طول می انجامد و بنابراین می تواند در اجرای معامله مورد غفلت واقع شود. نوع دوم تأخیرها می تواند به طور نامحدود طولانی مدت باشد ، مانند به روزرسانی (توییتر) معامله (T_2 ) در شکل 1a. ما مشاهده می کنیم که چنین تأخیر زمانی شکل می گیرد که عملیات غیر مصرفی توسط عملیات متناقض انجام شود و این مشاهدات را به عنوان ترتیب مضر اظهارات درگیری تدوین می کند.

تعریف 1

(ترتیب مضر اظهارات درگیری) فرض کنید که دو معامله متشکل از عبارات N و M توسط (T_1 = [S_1 ، S_2 ، ldots ، S_n] ) و (T_2 = [S_1 '، S_2' ، ldots مشخص شده است.، s_m '] ) ، یک ترتیب مضر از اظهارات درگیری در صورت وجود وجود دارد (1 le i

(s_i ) درگیری با (s_p ') و (s_j ) درگیری با (s_q' )

به عنوان مثال ، در لیست 1 ، جایی که (n = m = 6 ) ، یک ترتیب مضر از اظهارات درگیری با تنظیم (i = 1 ، ، j = 2 ، ، p = 1 ) و (q وجود دارد.= 6 ). شرط 1 به دلیل بروزرسانی (الفبای) و به روزرسانی (توییتر) (T_1 ) و (T_2 ) دو عمل متناقض هستند. شرط 2 و شرط 3 به دلیل وجود هیچ عملیاتی بین بروزرسانی (الفبای) و به روزرسانی (توییتر) در (T_1 ) وجود ندارد ، در حالی که عملیات دیگری بین بروزرسانی (الفبای) و بروزرسانی (توییتر) در (T_2 ) وجود دارد.

قضیه 1

هرگونه حباب در خط لوله معامله در اثر سفارش مضر اظهارات درگیری ایجاد می شود.

اثبات

خطوط لوله معامله بدون حباب باعث ایجاد اجرای بدون تأخیر نمی شود. این امر به این دلیل است که معاملات در موضوعات مختلف با همان سرعت پیش نمی روند. به عنوان مثال ، شکل 2 نشان می دهد که اگرچه هیچ حباب در خط لوله معامله وجود ندارد ، زیرا اجرای بروزرسانی در توییتر توییتر کمی بیشتر مصرف می کند ، اما معاملات به تأخیر می افتد. حتی اگر فرض کنید که اختلاف مدت هر عمل حداکثر ( Delta ) است ، معامله ای با عملیات N حداکثر به تأخیر می افتد. بنابراین میانگین تأخیر برای هر عمل ( دلتا ) است که محدود است. برای خط لوله معامله با حباب ، چنین ضمانتی وجود ندارد. بنابراین ، در این مقاله ، ما هدف ما از بین بردن ترتیب مضر است.

تأخیر در اجرای معامله

برای از بین بردن سفارش مضر ، برای تنظیم مجدد اظهارات در افزایش یا کاهش ترتیب مشاجره کار می کند. به این ترتیب ، شرط 2 در تعریف 1 در موارد کلی برگزار نمی شود. در این مقاله ، ما یک انتخاب دلخواه برای تغییر ترتیب در کاهش ترتیب مشاجره و آزمایش ها نشان می دهیم که این دو استراتژی با یکدیگر مطابقت دارند. با استفاده از این استراتژی برای لیست 1 ، لیست مرتب شده 2 و شکل 1B را به دست می آوریم و می توانیم ببینیم که هیچ تأخیری بیش از یک عمل وجود ندارد.

برای اجرای این استراتژی ، دو مانع وجود دارد: (1) تنظیم مجدد برخی از اظهارات ممکن است معناشناسی برنامه را نقض کند و (2) میزان مشاجره سریع در حال تغییر است و از قبل قابل دستیابی نیست. در مرحله بعد ، ما نشان می دهیم که چگونه می توان اظهارات را با خیال راحت و پویا میزان مشاجره را تخمین زد.

استخراج مجدد بلوک

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

تعریف 2

(بلوک مرتب سازی) با توجه به هر معامله به صورت دنباله ای از اظهارات (s = [s_1 ، s_2 ، ldots ، s_n] ) ، یک بلوک تنظیم مجدد B یک متوالی است (b = [s_ ، s_ ، ldots، s _] ) ، جایی که (1 le i_1

( texttt (s_) cap texttt (s ') = vacyyset ) به گونه ای که (s_ ) از نظر وابستگی خواندن پس از نوشتن به (s' ) بستگی ندارد.

( texttt (s_) cap texttt (s ') = vacyset ) به گونه ای که (s_ ) از نظر وابستگی نوشتن پس از خواندن به (s' ) بستگی ندارد.

( texttt (s_) cap texttt (s ') = vacyset ) به گونه ای که (s' ) و (s_ ) از نظر وابستگی نوشتن-پس از نوشتن به یکدیگر بستگی ندارند.

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

قضیه 2

با توجه به معامله و مجموعه ای از بلوک های مرتب سازی (<mathcal >= \) ، جایی که ( forall b ، b ' in<mathcal >) , (B cap B' = emptyset ) and (x08igcup _>>= S ) ، تنظیم مجدد بلوک های تنظیم مجدد ، در برنامه Serializable ، سریال سازی را به خطر نمی اندازد.

اثبات

با توجه به تعریف بلوک های مرتب سازی ، بلوک های مرتب سازی با یکدیگر مغایرت ندارند. به دنبال تئوری سریال سازی متناقض [37] ، این بلوک های مرتب سازی می توانند به طور خودسرانه دوباره تنظیم شوند به گونه ای که رفتار معامله تحت تأثیر قرار نگیرد.(مربع )

سه نوع وابستگی باید بر روی دستورات برنامه و دستورات SQL ردیابی شوند. برای مقابله با عبارات برنامه، استفاده از الگوریتم استاندارد جریان داده برای ما ساده است [26، 42]. برای سادگی، در این مقاله، if-statement و loop-statement را به عنوان یک عبارت کامل در نظر می گیریم، اگرچه تکنیک های پیچیده ای مانند فسیل حلقه می توانند ردیابی وابستگی ریز دانه را ایجاد کنند [39، 42]. در مورد پرس و جوهای SQL، ما دقیقاً روابط وابستگی بین ورودی و خروجی پرس و جو را مدل می کنیم:

انتخاب ساده بدون پرس و جوی فرعی: مجموعه خوانده شده تمام محمولات در عبارت Where را در بر می گیرد. جایی که عبارت به یک مجموعه خواندنی جهانی منجر می شود خالی است. مجموعه نوشتن روی خالی تنظیم شده است.

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

به روزرسانی ساده بدون پرسش های فرعی: مجموعه خوانده شده به عنوان «انتخاب ساده بدون پرسش های فرعی» تنظیم می شود. مجموعه نوشتن همان مجموعه خواندنی است.

به روز رسانی دیگر: مجموعه خوانده شده به عنوان "انتخاب های دیگر" تنظیم می شود. مجموعه نوشتن همان مجموعه خواندنی است.

طبق این قوانین، الگوریتم 1 نحوه تبدیل کد تراکنش را به بلوک های مرتب سازی مجدد نشان می دهد. ما به طور مکرر برای هر عبارت استفاده نشده بررسی می کنیم که کدام عبارات نمی توانند با آن مرتب شوند (خط 4-6). تمام عباراتی که نمی توانند یکدیگر را دوباره ترتیب دهند، یک بلوک ترتیب مجدد ایجاد می کنند (خط 11). الحاق، ترتیب اجرای اصلی عبارات را در هر بلوک مرتب سازی مجدد حفظ می کند (خط 9، جایی که (oplus ) نشان دهنده الحاق است). بعد از اینکه تمام عبارات با بلوک های مرتب سازی مجدد مشخص شدند، همه بلوک های مرتب سازی مجدد پیدا می شوند (خط 4،12). به عنوان مثال، برای تراکنش (T_1) در فهرست 1، همه گزاره ها به روزرسانی های ساده هستند و مجموعه خواندن و نوشتن این عبارات از هم جدا هستند. به این ترتیب، هر عبارت یک بلوک ترتیب مجدد ایجاد می کند. به عبارت دیگر، همه به روزرسانی ها را می توان خودسرانه مرتب کرد. در این مقاله، ما بر ترتیب مجدد انتخاب و به روز رسانی تمرکز می کنیم. روابط وابستگی سایر پرس و جوهای SQL را می توان بر این اساس تعریف کرد.

تخمین اختلاف

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

برای به دست آوردن میزان مشاجره یک بلوک تنظیم مجدد ، ابتدا میزان مشاجره هر بیانیه آن را تخمین می زنیم و از حداکثر به عنوان درجه مشاجره بلوک تنظیم شده استفاده می کنیم. به این ترتیب ، ما عملیات بسیار مورد نیاز را که با استفاده مجدد از بلوک ها با بسیاری از عملیات کمتر مورد آزمایش قرار می گیرد ، از دست نخواهیم داد. روش موجود از زمان انتظار و تغییر آن در هر بیانیه برای تخمین میزان مشاجره استفاده می کند [42]. این راه حل دارای دو کاستی است: (1) پیشخوان مجموعه برای هر بیانیه منحصر به فرد ، درجه واقعی مشاجره را برای بیانیه دست کم می گیرد. برای برنامه HFT ، هر عبارت معمولاً حاوی پارامترهای مختلف است. به عنوان مثال ، پرس و جو SQL برای به روزرسانی (الفبای ، 30) معمولاً به عنوان مقدار به روزرسانی سهام -= 30 ، قیمت = P که در آن SID = الفبای ، جایی که P آخرین قیمت ارائه شده توسط کاربر است ، فوری می شود. بنابراین ، بسیاری از اظهارات به روزرسانی همان مقدار و زمینه های قیمت در پیشخوان های مختلف شمارش می شوند.(2) تخمین زمان انتظار و واریانس آن از ریختن رنج می برد. این امر به این دلیل است که عملیات بسیار موردعلاقه به درستی مجدداً منتظر مدت طولانی نخواهد بود و بنابراین همیشه به عنوان عملیات کمتر مورد اعتراض طبقه بندی می شوند. سپس ، این عملیات تا پایان معامله قرار می گیرد و دوباره به عنوان عملیات به شدت مورد نیاز در نظر گرفته می شود. برای پرداختن به این دو موضوع ، ما یک تخمین مبتنی بر برنامه اجرا را پیشنهاد می کنیم که وقوع هر شی را در یک پنجره کشویی زمان جمع می کند.

مشاهده می کنیم که اگرچه عملیات متضاد ممکن است در SQL های مختلف نشان داده شود، اما آنها باید عملگر فیزیکی یکسانی را با اشاره به ویژگی های یکسان ایجاد کنند. به عنوان مثال، اگرچه به روزرسانی (Alphabet, 30) ممکن است قیمت های متفاوتی را به روزرسانی کند، اپراتور فیزیکی مربوطه آن نوع به روزرسانی را دارد و فیلدهای کمیت و قیمت یکسان را نشان می دهد. تنها تفاوت در پارامترهای مقادیر هدف است. از آنجایی که مشاجره فقط در عملگر قرار گرفته در سطح پایین طرح اجرا به شکل یک ساختار درختی رخ می دهد، کافی است یک شمارنده برای ثبت فرکانس وقوع برای هر عملگر فیزیکی در سطح پایین طرح اجرا اختصاص داده شود. الگوریتم 2 جزئیات اجرای شمارنده را شرح می دهد. اندازه پنجره کشویی زمان WS به شکاف های زمانی با دانه بندی g تقسیم می شود، به طوری که وقتی زمان جریان دارد، شکاف های زمانی بازیافت می شوند تا آخرین شمارش را منعکس کنند. هنگامی که یک اپراتور فیزیکی در سطح پایین برنامه اجرا ایجاد می شود، افزایش شمارنده مربوطه فراخوانی می شود. هنگامی که همه بلوک های مرتب سازی مجدد را استخراج می کنیم، Get را برای هر شمارنده در هر بلوک مرتب سازی مجدد فراخوانی می کنیم و حداکثر تعداد را به عنوان درجه اختلاف برای هر بلوک مرتب سازی مجدد انتخاب می کنیم.

تخصیص هر اپراتور فیزیکی با یک شمارنده ممکن است باعث هدر رفتن حافظه شود، به ویژه تحت بارهای کاری HFT که در آن اشیاء متضاد به سرعت در حال تغییر هستند به طوری که شمارنده تخصیص داده شده دیگر ممکن است در دوره زمانی بعدی استفاده نشود. برای رفع این نگرانی، ما یک استخر پیشخوان نگهداری می کنیم و هر بار که نیاز به اختصاص یک شمارنده جدید داریم، شمارنده ای را که در آخرین پنجره زمانی استفاده نشده است، بازیافت می کنیم.

مکانیسم شمارنده ما دو پارامتر برای تنظیم دارد. از منظر دقت درجه اختلاف، WS کمتر و متوسط مورد استقبال قرار می گیرد. این به این دلیل است که g و WS بزرگتر منجر به درجه منازعه بیات می شود و ترتیب مجدد ترتیب مضر را از بین نمی برد. WS خیلی کوچک در مقایسه با g، اطلاعات زیادی را از دست می دهد. از منظر سربار حافظه، WS بزرگ انتظار نمی رود. با این حال، g بسیار کوچک توسط سخت افزار ممنوع است. در این مقاله، آزمایش ها نشان می دهند که تنظیم ( ext = 1) s و (g = 100) ms تحت بارهای کاری HFT به خوبی کار می کند.

سفارش مجدد آفلاین

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

فرمول مسأله

مشکل تنظیم مجدد خارج از خط دارای دو انگیزه است. اول ، می تواند معاملات را ترتیب دهد تا همان سفارش مضر از معاملات مختلف با هم همپوشانی نداشته باشد. به این ترتیب ، اگرچه سفارش مضر هنوز وجود دارد ، اما آنها معاملات را مسدود نمی کنند. به عنوان مثال ، لیست 3 دو نوع معاملات را نشان می دهد. ما می توانیم ببینیم که معاملات هر دو نوع I و II فقط به صورت سریال قابل اجرا هستند. در عوض ، فرض کنید که چهار معامله (T_1 ) ، (T_2 ) ، (t_3 ) و (t_4 ) و (t_1 ) و (t_2 ) متعلق به نوع I و (است. T_3 ) و (T_4 ) متعلق به نوع II است. اگر به طور همزمان (t_1 ) و (t_3 ) را اجرا کنیم و بعد از اتمام آنها ، (t_3 ) و (t_4 ) را همزمان اجرا کنیم ، هیچ معامله ای مسدود نخواهد شد.

دوم ، اگر برخی از معاملات از اهمیت بیشتری برخوردار باشند ، می توان آنها را سریعتر انجام داد. لیست 4 این مورد را توصیف می کند. سه نوع معاملات وجود دارد. ما می توانیم ببینیم که دو نوع معاملات اول می توانند به طور همزمان اجرا شوند در حالی که دو نوع آخرین معاملات فقط به صورت سریال قابل اجرا هستند. با توجه به زمان ثابت ، اگر می خواهیم توان را به حداکثر برسانیم ، می خواهیم معاملات نوع I و II را تا حد امکان انجام دهیم و سپس معاملات نوع III را انجام دهیم. با این حال ، اگر پلت فرم بورس سهام بداند که درخواست کنندگان دو نوع معاملات آخر دوست دارند هزینه های بیشتری را برای انجام معاملات خود در طی یک ساعت بپردازند ، بازار سهام مایل است این دو نوع معاملات را در مدت زمان محدود انجام دهد.

برای تدوین این دو هدف ، هر برنامه می تواند به عنوان پیکربندی در جدول زمانی C از اندازه L تدوین شود. در اینجا ، ما از C برای مشخص کردن تعداد پردازنده ها و L طول طولانی ترین جدول زمانی استفاده می کنیم. هر شکاف در پیکربندی (c times l ) بیانیه ای از معاملات داده شده را نشان می دهد. اگر هر بیانیه معامله دقیقاً یک بار در پیکربندی پر شود و هنوز هم معناشناسی هر ترتیب سریال معاملات را حفظ کند ، ما یک پیکربندی معتبر داریم. ما یک پیکربندی را به شرح زیر تشکیل می دهیم.

تعریف 3

پیکربندی معتبر یک ماتریس با ردیف های L و ستون C است به گونه ای که شکاف در ردیف L-TH و ستون C-TH نشانگر یک عبارت منحصر به فرد از یک معامله است و معناشناسی هر ترتیب سریال معاملات را حفظ می کند.

پیکربندی بهینه از این رو به شرح زیر تعریف می شود:

تعریف 4

با توجه به مجموعه ای از معاملات ( mathcal ) و هزینه (f_t ) مرتبط با هر معامله (t in mathcal ) ، پیکربندی c را با اندازه t با توجه به ( mathcal ) پیدا کنید. به گونه ای که هزینه های جمع شده به حداکثر برسد:

به این ترتیب ، تنظیم مجدد خارج از خط با هدف یافتن یک پیکربندی بهینه برای مجموعه معاملات داده شده برای به حداکثر رساندن سود که پلت فرم بازار سهام می تواند داشته باشد. این مشکل بهینه سازی NP-Hard است.

قضیه 3

مشکل تنظیم مجدد خارج از خط NP-Hard است.

اثبات

ما ابتدا مشکل 0 1 کوله پشتی را معرفی می کنیم. در مشکل 0-1 1 مشکل ، n مورد وجود دارد و هر مورد من اندازه (s_i ) و هزینه (c_i ) دارد. نسخه تصمیم گیری از مشکل 0-1 Kyapsack تصمیم می گیرد که آیا زیر مجموعه ای از موارد را می توان با اندازه مساوی یا بیشتر از S با حداکثر هزینه M انتخاب کرد.

با توجه به نمونه ای از مشکل 0-1 Kyapsack ، ما یک نمونه تنظیم مجدد خارج از خط را به شرح زیر می سازیم. هر موردی که با یک معامله t مطابقت دارد. معامله T از به روزرسانی های (S_I ) در مورد سوابق مشخص (S_I ) تشکیل شده است که با سایر معاملات متفاوت است. اگر معامله بخواهد در صورت تکمیل معاملات در مدت زمان m / c ، درخواست کند (c_i ) بپردازد.

این دو مورد معادل هستند. اگر مشکل 0-1 Knapsack بتواند زیر مجموعه ای از موارد واجد شرایط را انتخاب کند ، معاملات مربوط به این موارد را می توان در مدت زمان C در یک پردازنده و حداقل وزن به پایان رساند. به این ترتیب ، ما می توانیم جدول زمانی را به طور مساوی به قطعات C تقسیم کنیم. این بخش ها باید معاملات را بر اساس مرز به روزرسانی های خود تقسیم کنند. به این ترتیب ، هر پردازنده می تواند عملیات را در هر قسمت با زمان m / c انجام دهد. اگر مشکل ما بتواند یک برنامه را پیدا کند ، می توانیم به صورت بی اهمیت عملیات را در یک دنباله ادغام کنیم و مربوط به زیر مجموعه ای از موارد باشد.

به این ترتیب ، ما مشکل 0/1 کوله پشتی را به مشکل تنظیم مجدد خارج از خط کاهش می دهیم. از آنجا که مشکل 0/1 Knapsack NP-Hard [20] است ، مشکل تنظیم مجدد خارج از خط ما نیز NP-Hard است.(مربع )

رویکرد مبتنی بر GA

در ابتدا ، ما یک الگوریتم ژنتیکی را برای حل مشکل تنظیم مجدد خارج از خط پیشنهاد می کنیم. الگوریتم ژنتیکی یک متا-هوریستی شناخته شده برای حل مشکلات بهینه سازی سخت است [38]. با توجه به بودجه محاسباتی برای هر تکرار ، تعدادی از روشهای تکراری اجرا می شود. ایده این است که افراد اولیه را تنظیم کنید و از تکامل افراد تقلید کنید تا متناسب ترین فرد را پیدا کنید. در اولین تکرار ، تعدادی از افراد انتخاب می شوند. در هر تکرار بیشتر ، افراد مورد ارزیابی قرار می گیرند و بهترین افراد برای تکامل انتخاب می شوند. تکامل با یک روش متقاطع انجام می شود. در هر متقاطع ، افراد منتخب بخش های مختلفی را مبادله می کنند تا فرد جدید ، که فرزندان خود را در نظر می گیرد ، دوست دارد بهتر از والدین خود ارزیابی شود. هر تکرار بودجه می گیرد و پس از خسته شدن بودجه ، فرد باقیمانده بازگردانده می شود.

در الگوریتم تنظیم مجدد خارج از خط مبتنی بر GA ، هر پیکربندی به عنوان یک فرد تعریف می شود. عملکرد تناسب اندام زمان کاملاً تأخیر آن است. در اولین تکرار ، ما به طور تصادفی m فردی تولید می کنیم. برای هر فرد ، معاملات به صورت تصادفی و یکنواخت به مجموعه های جدا شده C تقسیم می شوند. سپس ، برای هر پارتیشن ، معاملات در هر یک از مجموعه های C به طور تصادفی در یک دنباله طبقه بندی می شوند. به این ترتیب ، ما تنظیمات معتبر M را بدست می آوریم. در هر تکرار ، تمام تنظیمات به دست آمده از آخرین تکرار ارزیابی می شود. ما برای تکرار بعدی k را انتخاب می کنیم. هر دو تنظیم از تنظیمات K برای متقاطع برای تولید فرزندان استفاده می شود. به طور خاص ، یک پردازنده ابتدا به طور تصادفی انتخاب می شود و دو عمل به طور تصادفی انتخاب می شوند. اگر این دو عمل متعلق به واحدهای مختلف تنظیم مجدد باشد ، آنها تعویض می شوند. به همین ترتیب ، بلوک تنظیم مجدد و سفارش معامله آنها ممکن است نقض شود. به عنوان یک راه حل ، اگر یک عمل در وسط یک بلوک تنظیم مجدد قرار داشته باشد ، عملیات قبلی آن در بلوک تنظیم مجدد پیش از مکان جدید این عملیات قرار می گیرد. علاوه بر این ، در صورت نقض دستور معامله ، سایر عملیات از معاملات آسیب دیده بر این اساس پیش می رود. توجه داشته باشید که این ممکن است به روشی تکراری حاصل شود ، زیرا حرکت سایر عملیات پیش رو ممکن است دستور معامله را نیز نقض کند. ما M را به ظرفیت حافظه و k تنظیم می کنیم تا اطمینان حاصل شود که فرزندان تولید شده آنها هنوز هم می توانند در حافظه باشند.

با این حال ، راه حل مبتنی بر GA به سرعت در حداقل محلی به دام افتاد. آزمایش در فرقه. 5. 3 این استدلال را تأیید کنید.

رویکرد مبتنی بر SA

به عنوان یک راه حل ، ما یک الگوریتم احتمالی به نام SOR (الگوریتم تنظیم مجدد خارج از خط مبتنی بر بازپخت) را برای حل مشکل تنظیم مجدد خارج از خط پیشنهاد می کنیم. همانطور که در الگوریتم 3 نشان داده شده است ، SOR برای حل مشکل از خواص اساسی بازپخت شبیه سازی شده [21] استفاده می کند و تقریب ای از تنظیم مجدد بهینه خارج از خط ایجاد می کند.

در SOR ، هر پیکربندی معتبر با حالت الگوریتم مطابقت دارد. به طور شهودی ، پیکربندی "خوب" شبیه به پیکربندی بهتر دیگر (S ') است. چنین اکتشافی بدون جستجوی تمام حالتهای ممکن ، فضای جستجو را به شدت کاهش می دهد. در SOR ، انرژی یک دولت با زمان مصرفی آن اندازه گیری می شود. متفاوت از سایر الگوریتم های اکتشافی ساده ، SOR بین پذیرش یا رد احتمالی کشور همسایه تصمیم گیری می کند. در بتن ، با توجه به پیکربندی ، ما همچنین حالت همسایه آن را به عنوان تعویض تصادفی دو عمل در یک پردازنده انتخاب شده تصادفی و سپس تنظیم عملیات در بلوک های تنظیم مجدد مربوطه و معاملات تحت تأثیر تعریف می کنیم. توزیع احتمال پذیرش با برنامه بازپرداخت تعیین می شود. این تضمین می کند که SOR بعید است که در حداقل محلی نامطلوب محلی به دام بیفتد.

با توجه به معاملات و پیکربندی اولیه (S_0 ) ، SOR یک پیکربندی ارجح را برمی گرداند ، به طوری که زمان مصرفی معاملات به طور قابل توجهی کاهش می یابد. در الگوریتم 3 ، حلقه اصلی فرآیند جستجوی تکراری را بر اساس یک برنامه بازپخت ارائه شده در [21] نشان می دهد. عملکرد دما عملکرد اصلی برنامه بازپخت است. در این الگوریتم ، دما با سرعت (1 - cooling_rate) کاهش می یابد. عملکرد همسایه (ها) پیکربندی دیگری ایجاد می کند که دو بلوک تنظیم مجدد تصادفی از پیکربندی s را تعویض می کند.

SOR دارای سه پارامتر مهم است: دمای اولیه (T_0 ) ، Cooling_Rate و حداکثر تعداد تکرار حداکثر. این پارامترها به دنبال بهترین شیوه های بازپخت شبیه سازی شده تنظیم می شوند. پارامترها (T_0 ) و Cooling_Rate در ادبیات مورد مطالعه قرار گرفته اند [21] و همانطور که پیشنهاد شد ، ما (T_0 ) را تنظیم می کنیم تا کمی بزرگتر از زمان مصرفی اولیه باشد. پارامتر حداکثر تعداد تکرارهای اجرا شده در حلقه اصلی الگوریتم 3 را کنترل می کند. دمای نهایی در پایان اجرای الگوریتم (T_0 بار (1 - خنک کننده _rate)^). در این مقاله ، ما حداکثر را تنظیم می کنیم که دمای نهایی نزدیک به 0 باشد ، یعنی 0. 01 ٪ از اولیه (T_0 ).