توسعه دهندگان بسته‌های بهینه‌سازی در سال‌های اخیر فناوری پردازش موازی parallel computing به کمک کارت های گرافیکی نسل پیشرفته و قابلیت GPU computing را با حساسیت بالایی پیگیری می‌کنند. محدودیت‌های جدی در حل مسایل برنامه‌ریزی خطی linear programming، عدد صحیح integer programming و درجه دو quadratic programming با استفاده از پردازش GPU وجود دارد. شایان ذکر است که این امر تا این لحظه محقق نشده است. دلایل متعددی برای عدم تحقق این پدیده می‌توان عنوان کرد. این محدودیت‌ها در این پست بحث و بررسی می‌شود.
نرم‌افزارهای گروبی Gurobi و سیپلکس CPLEX و سایر بسته‌های بهینه‌سازی مشهور همگی از پردازش موازی به کمک CPU بهره‌مند هستند. بنابراین با توجه به تعداد هسته‌های CPU کامپیوتر، حل مساله در هسته‌های موازی می‌تواند صورت گیرد. البته بایستی توجه شود که هر الگوریتمی قابلیت موازی‌سازی را ندارد. ولی واقعا CPU و GPU به لحاظ سخت‌افزاری چه تفاوت‌های عمده‌ای می‌توانند داشته باشند که الگوریتمی که به کمک CPU قابلیت پردازش موازی را داشته باشد نتواند در GPU از چنین قابلیتی بهره‌مند شود؟
متاسفانه پردازنده‌های GPU برای محاسبات جبر خطی با ماتریس‌های فشرده sparse matrix مناسب نیستند. به عبارتی تجزیه کردن محاسبات جبر خطی بر روی ماتریس های فشرده کار آسانی نیست. در صورتی که این تجزیه امکان پذیر بود، هزاران عملیات به طور موازی بر روی پردازنده GPU قابل پردازش بود.
این فرم از محاسبات در واقع بنیان روش سیمپلکس است. شایان ذکر هست که روش سیمپلکس یکی از روش های پیشرو در حل مسایل برنامه‌ریزی خطی است. پردازنده‌های GPU مجهز به فناوری SMID یا single instruction, multiple data هستند. به عبارتی در صورتی که علمیات به بخش های یکسانی با حجم محاسبات یکسان تجزیه شوند، تمامی پردازنده های GPU این بخش های یکسان را در یک سیکل محاسباتی cycle (ولو با داده های ناهمگون) پردازش می‌کنند. عملیات حل یک مساله برنامه‌ریزی عدد صحیح MIP به کمک درخت شاخه و برش (حد) به این صورت قابل اجرا نمی‌ّباشد.
محاسبات در گره‌های درخت شاخه و برش در یک سیکل محاسباتی قابل پردازش نیست (اغلب عملیات به صورت سری انجام می‌گیرد) و طبیعتا فناوری SMID مناسب این منظور نخواهد بود.
مطمئنا این پله نهایی برای موازی‌سازی نخواهد بود و باید منتظر ماند و دید که در آینده متخخصین امر چه راه‌کارهایی برای این مواجهه با این چالش‌ها خلق خواهند نمود.
علی رغم اینکه موازی‌سازی به کمک پردازنده‌های GPU در حین فرایند بهینه‌سازی تابحال صورت نگرفته، ولی این بدین معنا نیست که یک متخصص بهینه‌سازی از این فناوری خود را محروم سازد. این فناوری می‌تواند تسهیلات خوبی برای محاسبات قبل و پس از عملیات بهینه‌سازی (پیش‌پردازش و پس‌پردازش) ارائه کند. به‌عنوان مثال کتابخانه‌هایی چون CUDA متعلق به شرکت Nvidia، یا NUMBA در پلتفرم پایتون Python قابلیت‌های جالبی در خصوص موازی‌سازی عملیات به شرط رعایت شرایط SMID ارائه می‌کند. به عنوان مثال محاسبه فواصل اقلیدسی بین مختصات ۱۰۰۰۰۰ شهر در یک مساله فروشنده دوره گرد travelling salesman problem یا TSP را در نظر بگیرید. ابتدا این عملیات بدون موازی‌سازی (در حالت سری و بدون در نظر گرفتن قابلیت SMID) محاسبه می‌گردد. کد پایتون زیر در هر بار عملیات تنها فاصله‌ی دو شهر را محاسبه می‌کند.
| import numpy as np | |
| from timeit import default_timer as timer | |
| def get_length(x1, y1, x2, y2): | |
| return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2) | |
| def build_graph(data): | |
| graph = {} | |
| for this in range(len(data)): | |
| for another_point in range(len(data)): | |
| if this != another_point: | |
| if this not in graph: | |
| graph[this] = {} | |
| graph[this][another_point] = get_length(data[this][0], data[this][1], data[another_point][0], | |
| data[another_point][1]) | |
| def main(): | |
| data = pd.read_csv("mona.csv",header=None).values.tolist() | |
| start = timer() | |
| graph = build_graph(data) | |
| duration = timer() - start | |
| print(duration) | |
| if __name__ == '__main__': | |
| main() |
در صورتی که کد زیر به کمک فناوری CUDA پردازنده‌ی کارت گرافیکی Nvidia و کتابخانه واسط pycu این عملیات را با سرعت بسیار زیادتر و زمان محاسباتی خیلی کمتر از حالت سری پردازش می‌کند.
| import numpy as np | |
| from timeit import default_timer as timer | |
| from numba import vectorize | |
| import pandas as pd | |
| @vectorize(['float32(float32, float32,float32, float32)'], target='cuda') | |
| def get_length(x1, y1, x2, y2): | |
| return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2) | |
| def build_graph(data): | |
| graph = {} | |
| for this in range(len(data)): | |
| for another_point in range(len(data)): | |
| if this != another_point: | |
| if this not in graph: | |
| graph[this] = {} | |
| graph[this][another_point] = get_length(data[this][0], data[this][1], data[another_point][0], | |
| data[another_point][1]) | |
| return graph | |
| def main(): | |
| data = pd.read_csv("mona.csv",header=None).values.tolist() | |
| start = timer() | |
| graph = build_graph(data) | |
| duration = timer() - start | |
| print(duration) | |
| if __name__ == '__main__': | |
| main() |
داده‌های مورد نیاز برای اجرای این کد:
http://www.math.uwaterloo.ca/tsp/data/ml/mona-lisa100K.tsp