سيلك

نشأت لغة البرمجة Cilk من ثلاثة مشاريع منفصلة في مختبر علوم الحاسوب التابع لمعهد ماساتشوستس للتكنولوجيا: ^{[ 3 ]}

• العمل النظري حول جدولة التطبيقات متعددة الخيوط.
• StarTech – برنامج شطرنج متوازٍ مصمم للعمل على جهاز الاتصال CM-5 التابع لشركة Thinking Machines Corporation.
• PCM/Threaded-C – حزمة برمجية مبنية على لغة C لجدولة سلاسل العمليات التي تعتمد على تمرير الاستمرارية على معالج CM-5

في أبريل 1994، دُمجت المشاريع الثلاثة وأُطلق عليها اسم "سيلك". اسم "سيلك" ليس اختصارًا، بل هو إشارة إلى "الخيوط الجميلة" ( الحرير ) ولغة البرمجة سي. صدر مُترجم سيلك-1 في سبتمبر 1994.

استندت لغة Cilk الأصلية إلى معيار ANSI C ، مع إضافة كلمات مفتاحية خاصة بـ Cilk للإشارة إلى التوازي. عند إزالة هذه الكلمات المفتاحية من شفرة Cilk المصدرية، تكون النتيجة دائمًا برنامج C صالحًا، يُسمى الحذف التسلسلي (أو حذف C ) لبرنامج Cilk الكامل، وله نفس دلالات برنامج Cilk الذي يعمل على معالج واحد. على الرغم من أوجه التشابه العديدة، فإن Cilk لا ترتبط ارتباطًا مباشرًا بلغة Concurrent C من مختبرات AT&T Bell .

تم تطوير Cilk كمترجم للغة C، مستهدفًا مُجمِّع GNU C (GCC). الإصدار الأخير، Cilk 5.4.6، متوفر من مختبر علوم الحاسوب والذكاء الاصطناعي التابع لمعهد ماساتشوستس للتكنولوجيا (CSAIL)، ولكنه لم يعد مدعومًا. ^{[ 4 ]}

كان برنامج Cilkchess للعب الشطرنج المتوازي بمثابة عرض لقدرات Cilk، والذي فاز بالعديد من جوائز الشطرنج الحاسوبي في التسعينيات، بما في ذلك بطولة هولندا المفتوحة للشطرنج الحاسوبي عام 1996. ^{[ 5 ]}

قبل عام 2006 تقريبًا، كان سوق لغة البرمجة Cilk مقتصرًا على الحوسبة عالية الأداء. ومع ظهور المعالجات متعددة النوى في الحوسبة السائدة، تم شحن مئات الملايين من أجهزة الكمبيوتر المتوازية الجديدة سنويًا. تأسست شركة Cilk Arts للاستفادة من هذه الفرصة: ففي عام 2006، أطلق ليسرسون شركة Cilk Arts لإنشاء وطرح نسخة حديثة من Cilk تلبي الاحتياجات التجارية لجيل جديد من المبرمجين. أغلقت الشركة جولة تمويل من الفئة (أ) في أكتوبر 2007، وتم شحن منتجها Cilk++ 1.0 في ديسمبر 2008.

يختلف Cilk++ عن Cilk في عدة جوانب: دعمه للغة C++، ودعمه للحلقات، ودعمه للكائنات الفائقة - وهي بنية جديدة مصممة لحل مشكلات تضارب البيانات الناتجة عن الوصول المتوازي إلى المتغيرات العامة. كان Cilk++ برنامجًا احتكاريًا . ومثل سابقه، تم تنفيذه كمترجم من Cilk إلى C++. وكان يدعم مترجمي Microsoft وGNU. 

في 31 يوليو 2009، أعلنت شركة Cilk Arts على موقعها الإلكتروني أن منتجاتها وفريقها الهندسي أصبحا جزءًا من شركة Intel. في أوائل عام 2010، بدأ موقع Cilk الإلكتروني www.cilk.comبإعادة التوجيه إلى موقع Intel (اعتبارًا من أوائل عام 2017، لم يعد موقع Cilk الأصلي يُحيل إلى مضيف). قامت Intel وCilk Arts بدمج التقنية وتطويرها، مما أدى إلى إصدار Intel Cilk Plus في سبتمبر 2010. ^{[ 6 ] [ 7 ]} يعتمد Cilk Plus على تبسيطات اقترحتها Cilk Arts في Cilk++، مما يُلغي الحاجة إلى العديد من الكلمات المفتاحية الأصلية في Cilk، مع إضافة إمكانية إنشاء الدوال والتعامل مع المتغيرات المستخدمة في عمليات الاختزال. يختلف Cilk Plus عن Cilk وCilk++ بإضافة امتدادات المصفوفات، ودمجه في مُصرّف تجاري (من Intel)، وتوافقه مع أدوات تصحيح الأخطاء الحالية. ^{[ 8 ]}

تم تطبيق Cilk Plus لأول مرة في مُصرّف Intel C++ مع إصدار مُصرّف Intel في Intel Composer XE 2010. وقدّمت Intel تطبيقًا مفتوح المصدر ( مرخصًا بموجب ترخيص BSD ) لمجموعة مُصرّفات GNU (GCC)، والتي تضمنت دعم Cilk Plus في الإصدار 4.9، ^{[ 9 ]} باستثناء الكلمة المفتاحية _Cilk_for ، التي أُضيفت في GCC 5.0. في فبراير 2013، أعلنت Intel عن نسخة مُعدّلة من Clang تدعم Cilk Plus. ^{[ 10 ]} يأتي مُصرّف Intel، وليس التطبيقات مفتوحة المصدر، مزودًا بأداة لكشف التزامن المتنافس ومحلل أداء.

أوقفت شركة إنتل دعمها لاحقاً، وأوصت مستخدميها بالتحول إلى استخدام OpenMP أو مكتبة TBB الخاصة بشركة إنتل لتلبية احتياجاتهم في البرمجة المتوازية. ^{[ 11 ]}

في تطبيق MIT Cilk الأصلي، كانت الكلمة المفتاحية الأولى هي `Cilk` cilk، والتي تُعرّف دالة مكتوبة بلغة Cilk. ولأن إجراءات Cilk تستطيع استدعاء إجراءات C مباشرةً، بينما لا تستطيع إجراءات C استدعاء أو إنشاء إجراءات Cilk مباشرةً، فإن هذه الكلمة المفتاحية ضرورية لتمييز كود Cilk عن كود C. أما Cilk Plus، فقد أزال هذا القيد، بالإضافة إلى cilkالكلمة المفتاحية `Cilk`، بحيث تستطيع دوال C وC++ استدعاء كود Cilk Plus والعكس صحيح.

في مايو 2017، تم إصدار GCC 7.1 مع إيقاف دعم Cilk Plus. ^{[ 12 ]} وأعلنت إنتل نفسها في سبتمبر 2017 أنها ستوقف دعم Cilk Plus مع إصدار أدوات تطوير البرمجيات من إنتل في عام 2018. ^{[ 11 ]} وفي مايو 2018، تم إصدار GCC 8.1 مع إزالة دعم Cilk Plus. ^{[ 13 ]}

بعد أن أوقفت إنتل دعم Cilk Plus، تولى معهد ماساتشوستس للتكنولوجيا تطوير Cilk في تطبيق OpenCilk، مع التركيز على نسخة LLVM/Clang المعدلة التي تُعرف الآن باسم "Tapir". ^{[ 11 ] [ 14 ]} ولا يزال OpenCilk متوافقًا إلى حد كبير مع Intel Cilk Plus. ^{[ 15 ]} وقد صدرت أول نسخة مستقرة منه في مارس 2021. ^{[ 16 ]}

الإضافة الرئيسية للغة Cilk إلى لغة C هي كلمتان رئيسيتان تسمحان معًا بكتابة برامج متوازية المهام.

• تشير الكلمة المفتاحية `spawn` ، عند استخدامها قبل استدعاء دالة (مثل ` spawn f(x)` )، إلى إمكانية تشغيل استدعاء الدالة ( f(x) ) بالتوازي مع التعليمات اللاحقة له في الدالة المستدعِية. تجدر الإشارة إلى أن المُجدوِل غير مُلزم بتشغيل هذا الإجراء بالتوازي؛ فالكلمة المفتاحية تُنبّهه فقط إلى إمكانية القيام بذلك.
• تشير عبارة التزامن إلى أنه لا يمكن استكمال تنفيذ الدالة الحالية حتى تكتمل جميع استدعاءات الدوال التي تم إنشاؤها مسبقًا. هذا مثال على أسلوب الحاجز .

(في Cilk Plus، يتم تهجئة الكلمات الرئيسية _Cilk_spawn و _Cilk_sync ، أو cilk_spawn و cilk_sync إذا تم تضمين رؤوس Cilk Plus.)

فيما يلي تطبيق تكراري لدالة فيبوناتشي في لغة سيلك، مع استدعاءات تكرارية متوازية، يوضح استخدام الكلمتين المفتاحيتين spawn و sync . كان الإصدار الأصلي من سيلك يتطلب إضافة تعليق توضيحي باستخدام الكلمة المفتاحية clik لأي دالة تستخدم هاتين الكلمتين ، وقد أُلغي هذا الشرط في إصدار سيلك بلس. (شفرة برنامج سيلك غير مرقمة؛ أُضيفت الأرقام فقط لتسهيل متابعة الشرح).

clik int fib ( int n ) {إذا كان ( ن < 2 ) {أعد n ؛}آخر {int x , y ;x = spawn fib ( n - 1 );y = spawn fib ( n - 2 );مزامنة ؛أعد x + y ;}}

إذا نُفِّذ هذا الكود بواسطة معالج واحد لتحديد قيمة fib(2) ، فسيُنشئ هذا المعالج إطارًا لـ fib(2) ، ويُنفِّذ الأسطر من 1 إلى 5. في السطر 6، سيُنشئ مساحات في الإطار لتخزين قيمتي x و y . في السطر 8، سيتعين على المعالج تعليق الإطار الحالي، وإنشاء إطار جديد لتنفيذ الإجراء fib(1) ، وتنفيذ كود ذلك الإطار حتى الوصول إلى عبارة الإرجاع، ثم استئناف إطار fib(2) مع وضع قيمة fib(1) في متغير x الخاص بـ fib(2) . في السطر التالي، سيحتاج إلى التعليق مرة أخرى لتنفيذ fib(0) ووضع النتيجة في متغير y الخاص بـ fib(2) .

عند تنفيذ الكود على جهاز متعدد المعالجات ، يختلف مسار التنفيذ. يبدأ أحد المعالجات بتنفيذ fib(2) ؛ وعند وصوله إلى السطر 8، تُشير الكلمة المفتاحية spawn ، التي تُعدّل استدعاء fib(n-1)، إلى أنه يُمكنه إسناد المهمة بأمان إلى معالج ثانٍ: يستطيع هذا المعالج الثاني إنشاء إطار لـ fib(1) ، وتنفيذ كوده، وتخزين نتيجته في إطار fib(2) عند انتهائه؛ بينما يُواصل المعالج الأول تنفيذ كود fib(2) في الوقت نفسه. لا يُلزم المعالج بتخصيص إجراء مُنشأ في مكان آخر؛ فإذا كان الجهاز يحتوي على معالجين فقط، وكان الثاني لا يزال مشغولاً بـ fib(1) عندما يصل المعالج الذي يُنفذ fib(2) إلى استدعاء الإجراء، فسيُعلّق المعالج الأول تنفيذ fib(2) ويُنفذ fib(0) بنفسه، كما لو كان المعالج الوحيد. بالطبع، إذا كان هناك معالج آخر متاح، فسيتم استدعاؤه للخدمة، وستقوم المعالجات الثلاثة بتنفيذ إطارات منفصلة في وقت واحد.

(الوصف السابق ليس دقيقًا تمامًا. على الرغم من أن المصطلحات الشائعة لمناقشة Cilk تشير إلى المعالجات التي تتخذ قرارًا بتفويض العمل إلى معالجات أخرى، إلا أن المجدول هو الذي يخصص الإجراءات للمعالجات للتنفيذ، باستخدام سياسة تسمى سرقة العمل ، والتي سيتم وصفها لاحقًا.)

إذا قام المعالج الذي يُنفذ fib(2) بتنفيذ السطر 13 قبل أن يُكمل المعالجان الآخران إطاراتهما، فسيُنتج نتيجة غير صحيحة أو خطأً؛ إذ سيحاول fib(2) جمع القيم المخزنة في x و y ، لكن إحدى هاتين القيمتين أو كلتيهما ستكون مفقودة. هذا هو الغرض من الكلمة المفتاحية sync ، التي نراها في السطر 11: فهي تُخبر المعالج الذي يُنفذ إطارًا ما بأنه يجب عليه تعليق تنفيذه حتى تُنهي جميع استدعاءات الإجراءات التي أنشأها عملها. عندما يُسمح لـ fib(2) بالمتابعة بعد عبارة sync في السطر 11، فإن ذلك لا يكون إلا لأن fib(1) و fib(0) قد أكملا عملهما ووضعا نتائجهما في x و y ، مما يجعل إجراء العمليات الحسابية على تلك النتائج آمنًا.

يستخدم مثال الكود أعلاه صيغة Cilk-5. أما Cilk الأصلي (Cilk-1) فقد استخدم صيغة مختلفة تمامًا تتطلب البرمجة بأسلوب تمرير الاستمرارية الصريح ، وتبدو أمثلة فيبوناتشي كما يلي: ^{[ 17 ]}

thread fib ( cont int k , int n ) { if ( n < 2 ) { send_argument ( k , n ); } else { cont int x , y ; spawn_next sum ( k , ? x , ? y ); spawn fib ( x , n - 1 ); spawn fib ( y , n - 2 ); } }thread sum ( cont int k , int x , int y ) { send_argument ( k , x + y ); }

في حالة التكرار ضمن دالة fib ، تشير الكلمة المفتاحية spawn_next إلى إنشاء سلسلة عمليات لاحقة (بدلاً من سلاسل العمليات الفرعية التي تُنشئها دالة spawn )، والتي تُنفذ روتين الجمع الفرعي بعد انتظار ملء متغيري الاستمرار x و y بواسطة الاستدعاءات التكرارية. تستخدم الحالة الأساسية وروتين الجمع عملية send_argument(k, n) لتعيين قيمة متغير الاستمرار k إلى قيمة n ، مما يُعيد القيمة فعليًا إلى سلسلة العمليات اللاحقة.

الكلمتان المفتاحيتان المتبقيتان في لغة Cilk أكثر تعقيدًا بعض الشيء، وتتعلقان باستخدام المدخلات . عادةً، عند إنشاء إجراء Cilk، لا يمكنه إعادة نتائجه إلى الإجراء الأصلي إلا بوضع تلك النتائج في متغير ضمن إطار الإجراء الأصلي، كما فعلنا في المثال عندما أسندنا نتائج استدعاءات الإجراءات المُنشأة إلى ` xand` y.

البديل هو استخدام دالة مُدخلة. الدالة المُدخلة هي دالة داخلية ضمن إجراء Cilk، تتولى معالجة نتائج استدعاء الإجراء المُنشأ عند عودتها. أحد الأسباب الرئيسية لاستخدام الدوال المُدخلة هو ضمان عمل جميع دوال الإجراء بشكل ذري فيما بينها ومع الإجراء الأصلي، مما يجنب حدوث الأخطاء التي قد تظهر إذا حاولت عدة إجراءات مُعادة تحديث نفس المتغيرات في الإطار الأصلي في الوقت نفسه.

• تحدد الكلمة inletالمفتاحية وظيفة معينة داخل الإجراء كمدخل.
• لا يمكن استخدام الكلمة abortالمفتاحية إلا داخل المدخل؛ فهي تخبر المجدول بأنه يمكن إجهاض أي إجراءات أخرى تم إنشاؤها بواسطة الإجراء الأصل بأمان.

تمت إزالة المداخل عندما أصبح Cilk هو Cilk++، وهي غير موجودة في Cilk Plus.

أضافت لغة Cilk++ بنيةً إضافية، وهي الحلقة المتوازية، والتي يُشار إليها بـ clik_for في Cilk Plus. تبدو هذه الحلقات كالتالي:

void loop ( int * a , int n ){#pragma clik grainsize = 100 // اختياريclick_for ( int i = 0 ; i < n ; i ++ ) {a [ i ] = f ( a [ i ]);}}

يُطبّق هذا الأسلوبَ المُتّبع في الخرائط المتوازية : يُنفّذ جسم الحلقة، وهو هنا استدعاء للدالة f متبوعًا بتعيين قيمة للمصفوفة a ، لكل قيمة من قيم i من صفر إلى n بترتيب غير مُحدّد. يُحدّد التوجيه البرمجي الاختياري "حجم الحبيبة" عمليةَ التجميع : تُعالَج أي مصفوفة فرعية تحتوي على مئة عنصر أو أقل بالتسلسل. على الرغم من أن مواصفات Cilk لا تُحدّد السلوك الدقيق لهذا البناء، إلا أن التنفيذ النموذجي هو عبارة عن استدعاء ذاتي لتقسيم المشكلة وحلّها، ^{[ 18 ]} كما لو أن المبرمج قد كتب

static void recursion ( int * a , int start , int end ) { if ( end - start <= 100 ) { // الـ 100 هنا هو حجم الحبيبة. for ( int i = start ; i < end ; i ++ ) { a [ i ] = f ( a [ i ]); } } else { int midpoint = start + ( end - start ) / 2 ; clik_spawn recursion ( a , start , midpoint ); recursion ( a , midpoint , end ); clik_sync ; } }void loop ( int * a , int n ) { recursion ( a , 0 , n ); }

تكمن أسباب إنشاء برنامج قائم على أسلوب فرق تسد بدلاً من البديل الواضح، وهو حلقة تستدعي جسم الحلقة كدالة، في كل من التعامل مع حجم الحبيبات والكفاءة: فإجراء كل عمليات التوليد في مهمة واحدة يجعل موازنة الحمل عنق زجاجة. ^{[ 19 ]}

أظهرت مراجعةٌ لبنى الحلقات المتوازية المختلفة على موقع HPCwire أن بنية cilk_for عامةٌ إلى حدٍ كبير، لكنها أشارت إلى أن مواصفات Cilk Plus لم تنص على ضرورة أن تكون تكراراتها مستقلةً عن البيانات، لذا لا يمكن للمترجم تحويل حلقة cilk_for إلى متجهٍ تلقائيًا . كما أشارت المراجعة إلى أن عمليات الاختزال (مثل عمليات الجمع على المصفوفات) تتطلب شيفرةً إضافية. ^{[ 18 ]}

أضافت لغة Cilk++ نوعًا من الكائنات يُسمى الكائنات الفائقة ، والتي تسمح لعدة مسارات بمشاركة الحالة دون حدوث تضارب في البيانات ودون استخدام أقفال صريحة. يمتلك كل مسار عرضًا على الكائن الفائق يمكنه استخدامه وتحديثه؛ وعندما تتزامن المسارات، يتم دمج العروض بطريقة يحددها المبرمج. ^{[ 20 ]}

أكثر أنواع الكائنات الفائقة شيوعًا هو المُختزِل، والذي يُقابل عبارة الاختزال في OpenMP أو المفهوم الجبري للمونويد . يحتوي كل مُختزِل على عنصر محايد وعملية تجميعية تجمع قيمتين. المُختزِل النموذجي هو جمع الأعداد: العنصر المحايد هو صفر، وعملية الاختزال التجميعية تحسب المجموع. هذا المُختزِل مُدمج في Cilk++ وCilk Plus.

// حساب مجموع foo(i) لكل i من 0 إلى N، بالتوازي. cilk :: reducer_opadd <float> result ( 0 ); cilk_for ( int i = 0 ; i < N ; i ++ ) result += foo ( i ) ;

يمكن استخدام أدوات الاختزال الأخرى لإنشاء قوائم مرتبطة أو سلاسل نصية، ويمكن للمبرمجين تعريف أدوات اختزال مخصصة.

من عيوب الكائنات الفائقة أنها توفر حتمية محدودة فقط . يشير بوركهارت وآخرون إلى أن حتى مُختزل المجموع يمكن أن يؤدي إلى سلوك غير حتمي، حيث يعرضون برنامجًا قد ينتج إما 1 أو 2 اعتمادًا على ترتيب الجدولة: ^{[ 21 ]}

void add1 ( cilk :: reducer_opadd < int > & r ) { r ++ ; } // ... cilk :: reducer_opadd < int > r ( 0 ); cilk_spawn add1 ( r ); if ( r == 0 ) { r ++ ; } cilk_sync ; output ( r . get_value ());

تضيف Intel Cilk Plus رموزًا للتعبير عن العمليات عالية المستوى على المصفوفات بأكملها أو أجزاء منها ؛ على سبيل المثال، دالة على نمط axpy تُكتب عادةً

// y ← α x + y void axpy ( int n , float alpha , const float * x , float * y ) { for ( int i = 0 ; i < n ; i ++ ) { y [ i ] += alpha * x [ i ]; } }

يمكن التعبير عنها في Cilk Plus على النحو التالي:

y[0:n] += alpha * x[0:n];

تساعد هذه الصيغة المُصرّف على تحويل التطبيق إلى صيغة متجهة بكفاءة. يسمح معالج Intel Cilk Plus بتطبيق عمليات C/C++ على عناصر مصفوفة متعددة بالتوازي، كما يوفر مجموعة من الدوال المدمجة التي يمكن استخدامها لإجراء عمليات الإزاحة والتدوير والاختزال المتجهة. توجد وظائف مشابهة في Fortran 90 ؛ ويكمن الاختلاف في Cilk Plus في أنه لا يُخصص مصفوفات مؤقتة، مما يُسهّل التنبؤ باستخدام الذاكرة.

في لغة Cilk Plus، الدالة الأساسية هي دالة عادية يمكن استدعاؤها إما على وسائط عددية أو على عناصر مصفوفة بالتوازي. وهي تشبه دوال النواة في OpenCL .

يُتيح هذا التوجيه البرمجي للمُصرّف إمكانية تحويل حلقة التكرار إلى صيغة متجهة حتى في الحالات التي قد تفشل فيها عملية التحويل التلقائي. إنها أبسط طريقة لتطبيق التحويل إلى صيغة متجهة يدويًا.