VSUM: جمع بندی آرایه سریع در C

vsum یک کتابخانه منبع باز است که برای آن طراحی شده است جمع بندی با کارایی بالا از آرایه های عددیبشر طراحی شده برای برنامه های کاربردی شامل مجموعه داده های بزرگ ، محاسبات علمی و سیستم های بحرانی عملکرد ، اهرم های VSUM چند رشتهبا وکتور سازی SIMD (AVX/AVX2/SSE2)وت الگوریتم های حافظه پنهان برای دستیابی به سرعت قابل توجهی در مورد پیاده سازی های ساده لوح.

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

ویژگی های اصلی

• پشتیبانی نوع: روال بهینه شده برای intبا floatوت double آرایه ها
• اعدام موازی: از موضوعات POSIX برای جمع بندی همزمان در پردازنده های چند هسته ای استفاده می کند.
• شتاب سیم: به کار می رود AVX2 ، AVX ، SSE2 و SSE Intrinsics با تشخیص ویژگی CPU Time Time برای محاسبات بردار در معماری سازگار x86-64.
• پردازش پی در پی آگاه حافظه نهان: شامل یک روش جمع بندی متوالی است که با مکان حافظه پنهان در ذهن طراحی شده است.
• اجرای تطبیقی: به طور خودکار مناسب ترین استراتژی جمع بندی (SIMD ، موازی ، پی در پی) را بر اساس قابلیت های سخت افزار زمان اجرا و ویژگی های داده انتخاب می کند.
• سهولت ادغام: ارائه شده به عنوان .h هدر و .c پرونده منبع برای ورود ساده در پروژه های C.
• قابلیت حمل: سازگار با لینوکس ، مکوس و سایر سیستم های سازگار با POSIX که از pthreads پشتیبانی می کنند. شتاب SIMD مخصوص x86-64 است ، و دارای عقب نشینی های برازنده در سایر معماری ها است.

گزاره ارزش فنی

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

• استفاده مؤثر از ذاتی SIMD برای عملیات حسابی داده های موازی.
• تشخیص ویژگی CPU زمان اجرا قابل حمل برای اطمینان از استفاده از دستورالعمل SIMD ایمن و بهینه.
• استراتژی های توزیع بار کار برای اجرای چند رشته ای.
• ملاحظات تراز حافظه برای به حداکثر رساندن کارآیی SIMD.
• اصول کد C تمیز ، مدولار و به خوبی مستند برای حفظ و استفاده مجدد

نصب و ساخت فرآیند

1. کد منبع را بدست آورید:

   git clone https://github.com/davidesantangelo/vsum.git
   cd vsum
   

2. در پروژه خود ادغام کنید: اضافه کردن vsum.h وت vsum.c به پرونده های منبع پروژه خود.

3. کامپایل: ساخت vsum.c به یک فایل شی. برای عملکرد بهینه در x86-64 ، مجموعه دستورالعمل های مربوط به SIMD را فعال کنید (به عنوان مثال ، -mavx2) و pthreads (-pthread). این کتابخانه شامل چک های زمان اجرا است ، و حتی اگر دستگاه هدف فاقد ویژگی ها باشد ، تهیه آن با این پرچم ها ایمن است.

   # Example: Compile vsum.c with AVX2 and pthreads support
   gcc -O2 -Wall -Wextra -pthread -mavx2 -c vsum.c -o vsum.o
   

4. پیوند: نتیجه را پیوند دهید vsum.o فایل شی با کد برنامه خود. اطمینان حاصل کنید که با کتابخانه pthreads پیوند دارید (-pthread).

   # Example: Compile main application and link with vsum.o and pthreads
   gcc -O2 -Wall -Wextra -pthread main.c vsum.o -o my_application -lm # -lm if using math functions
   

مثال استفاده

#include "vsum.h" // Include the library header
#include 
#include  // For aligned_alloc, free
#include  // For int64_t

int main() {
    size_t n = 10000000; // Example array size
    // Allocate memory aligned for potential SIMD optimization
    int *arr = (int*)aligned_alloc(VSUM_AVX_ALIGNMENT, n * sizeof(int));
    if (!arr) { perror("aligned_alloc failed"); return 1; }

    // Initialize array data (example)
    for (size_t i = 0; i < n; ++i) {
        arr[i] = (int)(i % 100);
    }

    // Utilize different summation strategies
    int64_t sum_parallel = vsum_parallel_sum_int(arr, n);
    int64_t sum_simd = vsum_simd_sum_int(arr, n);
    int64_t sum_cache = vsum_cache_friendly_sum_int(arr, n);

    printf("Parallel Sum Result: %lld\n", sum_parallel);
    printf("SIMD Sum Result:     %lld\n", sum_simd);
    printf("Cache Sum Result:    %lld\n", sum_cache);

    free(arr); // Release allocated memory
    return 0;
}

خصوصیات عملکرد

VSUM می تواند در مقایسه با حلقه های جمع بندی متوالی ساده لوح ، به ویژه در آرایه های بزرگ پردازش شده بر روی CPU های چند هسته ای مجهز به قابلیت AVX2 ، به پیشرفت های قابل توجهی برسد. سرعت های مختلف از 10x تا 50x در شرایط بهینه امکان پذیر هستند.

(ارقام عملکرد به شدت به سخت افزار خاص ، کامپایلر ، اندازه داده ها و بار سیستم بستگی دارد. به پروژه مراجعه کنید README.md برای معیارهای دقیق.)

جزئیات اجرای

1 چند رشته (جمع بندی موازی)

در vsum_parallel_sum_* توابع آرایه ورودی را به بخش ها تقسیم می کند. هر بخش توسط یک موضوع کارگر جداگانه با استفاده از موضوعات POSIX پردازش می شود. مبالغ جزئی از هر موضوع برای تولید نتیجه نهایی جمع می شود. تعداد موضوعات به صورت پویا بر اساس اندازه داده ها و هسته های موجود ، تحت پوشش قرار می گیرد. VSUM_MAX_THREADSبشر

// Example function signature
int64_t vsum_parallel_sum_int(const int *array, size_t total_elements);

2 وکتور سازی SIMD (جمع بندی SIMD)

در vsum_simd_sum_* توابع با استفاده از دستورالعمل منفرد ، داده های متعدد (SIMD) ذاتی (AVX2 ، AVX ، SSE2 ، SSE) موجود در پردازنده های x86-64. چک های زمان اجرا (cpuid) اطمینان حاصل کنید که فقط دستورالعمل های پشتیبانی شده اجرا می شوند. اجرای بالاترین مجموعه دستورالعمل موجود (ترجیح AVX2> AVX> SSE2> SSE) را انتخاب می کند و داده ها را در تکه های بردار پردازش می کند (به عنوان مثال ، 8 عدد صحیح یا 4 دو برابر همزمان با AVX2). در صورت لزوم ، تراز حافظه را برای عملکرد بهینه انجام می دهد ، و در صورت لزوم به بارهای غیرقابل توصیف می افتد. پردازش مقیاس به عنوان یک برگشتی نهایی استفاده می شود.

// Example function signature
int64_t vsum_simd_sum_int(const int *array, size_t total_elements);

3 جمع بندی پی در پی دوستانه حافظه نهان

در vsum_cache_friendly_sum_* توابع یک جمع متوالی را انجام می دهند اما داده های فرآیند را در تکه هایی که تقریباً مربوط به اندازه خط حافظه حافظه پنهان CPU معمولی است ((VSUM_CACHE_LINE_SIZE). این هدف برای بهبود محل داده ها و کاهش از دست دادن حافظه پنهان در مقایسه با یک حلقه کاملاً ساده لوح است ، اگرچه پیش نویس های CPU مدرن اغلب نیاز به مسدود کردن حافظه پنهان دستی را در جمع بندی ساده کاهش می دهند.

// Example function signature
int64_t vsum_cache_friendly_sum_int(const int *array, size_t total_elements);

مرجع API

این کتابخانه توابع را برای هر استراتژی جمع بندی و نوع داده ها در معرض نمایش قرار می دهد:

جمع بندی موازی:

• vsum_parallel_sum_int(const int *array, size_t n)
• vsum_parallel_sum_float(const float *array, size_t n)
• vsum_parallel_sum_double(const double *array, size_t n)

جمع بندی سیمد:

• vsum_simd_sum_int(const int *array, size_t n)
• vsum_simd_sum_float(const float *array, size_t n)
• vsum_simd_sum_double(const double *array, size_t n)

جمع بندی متوالی دوستانه حافظه نهان:

• vsum_cache_friendly_sum_int(const int *array, size_t n)
• vsum_cache_friendly_sum_float(const float *array, size_t n)
• vsum_cache_friendly_sum_double(const double *array, size_t n)

همه توابع به یک نشانگر به آرایه داده و تعداد کل عناصر نیاز دارند (n). مبالغ عدد صحیح بازگشت int64_t برای جلوگیری از سرریز. مبالغ معکوس بازده double برای دقت پیشرفته

مثال: جمع بندی Simd با نقطه شناور

// Assume 'float_array' is a pointer to your float data and 'num_elements' is its size.
float *float_array = /* ... allocation and initialization ... */;
size_t num_elements = /* ... size of array ... */;

// Calculate the sum using the SIMD-optimized function.
// VSUM automatically detects AVX/SSE support and uses the best available path.
double sum_result = vsum_simd_sum_float(float_array, num_elements);

printf("SIMD Sum of float array: %f\n", sum_result);

ملاحظات فنی

• تشخیص ویژگی پردازنده زمان اجرا: استفاده می کند cpuid در X86-64 برای فعال کردن مسیرهای SIMD ، اطمینان از قابلیت حمل و جلوگیری از خطاهای دستورالعمل غیرقانونی.
• تراز حافظه: توابع SIMD بهترین عملکرد را با حافظه تراز شده با عرض بردار (به عنوان مثال ، 32 بایت برای AVX) انجام می دهند. VSUM_AVX_ALIGNMENT ثابت ارائه شده است در صورت امکان از بارهای تراز استفاده می شود. بارهای بدون مجوز به عنوان یک بازپرداخت عمل می کنند.
• سرریز: جمع بندی عدد صحیح استفاده می کند int64_t باتری ها برای رسیدگی به مبالغ زیاد بدون سرریز.
• دقت نقطه شناور: جمع آوری های نقطه شناور استفاده کنید double برای تجمع در صورت لزوم برای کاهش ضرر دقیق.
• رسیدگی به خطا: چک های اساسی برای نشانگرهای تهی و عناصر صفر گنجانده شده است. خطاهای ایجاد موضوع گزارش شده است stderrبشر

دستورالعمل مشارکت

مشارکت از طریق مسائل GitHub و درخواست های کشش استقبال می شود. لطفاً برای هرگونه دستورالعمل مشارکت خاص به مخزن پروژه مراجعه کنید.

مجوز

VSUM تحت مجوز BSD 2-Clause توزیع می شود. دیدن LICENSE پرونده برای جزئیات کامل

پایان

VSUM یک راه حل قوی و کارآمد برای جمع بندی آرایه در C ارائه می دهد ، و برنامه های کاربردی عملی از چندتایی ، بهینه سازی SIMD و برنامه نویسی آگاهانه را نشان می دهد. این مناسب برای توسعه دهندگان که به دنبال تسریع در محاسبات عددی یا کشف تکنیک های پیشرفته بهینه سازی سیستم هستند.

مخزن را کاوش کرده و VSUM را در پروژه های خود ادغام کنید:

git clone https://github.com/davidesantangelo/vsum.git