بهینه سازی و فناوری پردازش گرافیکی GPU

 

توسعه دهندگان بسته‌های بهینه‌سازی در سال‌های اخیر فناوری پردازش موازی 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

0 Comments
Inline Feedbacks
View all comments