قياس الوقت بدقة النانو ثانية

قبل شهرين جاءت لحظة تاريخية بالنسبة لي. لم تعد أدوات نظام التشغيل القياسية لقياس الوقت كافية بالنسبة لي. استغرق الأمر وقتًا لقياس الدقة النانوية والثانوية.

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

نظرًا لأنه يمكنك قياس العديد من أنواع الوقت المختلفة على جهاز الكمبيوتر ، فسأوضح على الفور أننا سنتحدث هنا عن "الوقت بواسطة ساعة الإيقاف". أو وقت ساعة الحائط. إنه الوقت الفعلي ، الوقت المنقضي ، إلخ. أي وقت "بشري" بسيط نكتشفه في بداية المهمة ونتوقف عند النهاية.

ميكروثانية - إلى الأبد تقريبا

اعتاد مطورو الأنظمة عالية الأداء على مدى السنوات القليلة الماضية على النطاق الزمني للميكروثانية. بالميكروثانية ، يمكنك قراءة البيانات من محرك أقراص NVMe. بالميكروثانية ، يمكن إرسال البيانات عبر الشبكة. ليس للجميع بالطبع ، ولكن لشبكة InifiniBand - بسهولة.

في الوقت نفسه ، كان للميكروثانية أيضًا بنية. يتكون مكدس الإدخال / الإخراج الكامل من العديد من مكونات البرامج والأجهزة. التأخير الذي يحدثه البعض منهم يقع على مستوى ما دون الثانية.

لقياس التأخيرات بهذا الحجم ، لم تعد دقة الميكروثانية كافية. ومع ذلك ، ليست الدقة فقط مهمة ، ولكن أيضًا النفقات العامة لقياس الوقت. إرجاع استدعاء نظام clock_gettime () Linux الوقت بدقة nanosecond. على جهاز موجود في متناول يدي (Intel® Xeon® CPU E5-2630 v2 @ 2.60GHz) ، تكتمل هذه المكالمة في حوالي 120 نانو ثانية. شخصية جيدة جدا. بالإضافة إلى ذلك ، تعمل clock_gettime () بشكل متوقع. هذا يسمح لك أن تأخذ في الاعتبار النفقات العامة لدعوته وأخذ القياسات في الواقع بدقة ترتيب عشرات عشرات النانو ثانية. ومع ذلك ، دعونا ننتبه الآن لذلك. لقياس الفاصل الزمني ، تحتاج إلى إجراء مكالمتين من هذا القبيل: في البداية وفي النهاية. على سبيل المثال قضاء 240 نانوثانية. إذا تم قياس فترات زمنية متباعدة بشكل مكثف بترتيب 1-10 ميكرومتر ، فإن عملية القياس نفسها في بعض الحالات ستشوه العملية المرصودة بشكل كبير.

لقد بدأت هذا القسم بكيفية تسارع مكدس IO في السنوات الأخيرة. هذا جديد ، ولكنه بعيد عن السبب الوحيد لرغبتك في قياس الوقت بسرعة وبدقة. كانت مثل هذه الحاجة دائما. على سبيل المثال ، كان هناك دائمًا رمز أردت تسريع دورة ساعة واحدة على الأقل من المعالج. أو مثال آخر ، من المقالة الأصلية حول ثغرة Spectre المثيرة:



هنا ، تقيس الأسطر 72-74 وقت تنفيذ عملية وصول واحدة للذاكرة. صحيح أن سبيكتر لا يهتم بالثواني النانوية. يمكن قياس الوقت بـ "الببغاوات". سنعود إلى الببغاوات والثواني.

عداد طابع زمني

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

1. x86 عداد ختم الوقت
2. تسجيل قاعدة زمنية على PowerPC
3. عداد الوقت الفاصل على Itanium
4. الخ.

أدناه سأستخدم دائمًا اسم "عداد الطابع الزمني" أو TSC ، على الرغم من أنني في الواقع سأضع في اعتبارك أي عداد من هذا القبيل ، بغض النظر عن الهندسة المعمارية.

قراءة قيمة TSC عادة - ولكن مرة أخرى ليس دائمًا - ممكن مع تعليمات واحدة. هنا مثال لـ x86. بالمعنى الدقيق للكلمة ، هذه ليست تعليمات تجميع نقية ، لكن مجمع غنو المضمّن:

uint32_t eax, edx; __asm__ __volatile__( "rdtsc" : "=a" (eax), "=d" (edx)); 

تضع تعليمات rdtsc نصفين 32 بت من سجل TSC في سجلات eax و edx. من بينها ، يمكنك "لصق" قيمة واحدة 64 بت.

ألاحظ مرة أخرى: يمكن استدعاء هذه التعليمات (وما شابه) في معظم الحالات مباشرة من مساحة المستخدم. لا توجد مكالمات نظام. النفقات العامة الدنيا.

ما الذي يجب فعله الآن لقياس الوقت؟

1. تنفيذ أحد هذه التعليمات في بداية الفترة الزمنية التي تهمنا. تذكر قيمة العداد
2. تنفيذ تعليمات من هذا القبيل في النهاية. نعتقد أن قيمة العداد من التعليمات الأولى إلى الثانية ستزداد. خلاف ذلك ، لماذا هو مطلوب؟ تذكر القيمة الثانية
3. نحن نعتبر الفرق بين القيمتين المخزنتين. هذا وقتنا

يبدو بسيطا ، ولكن ...

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

ولكن ماذا لو لم تكن هناك حاجة إلى الببغاوات ، لكن الثواني / الميكروثانية / النانو ثانية ، وما إلى ذلك؟ يمكن تمييز حالتين مختلفتين جوهريًا هنا:

1. نانوثانية مطلوبة ، ولكن بعد ذلك. أي أنه يجوز أولاً إجراء جميع القياسات اللازمة في الببغاوات وتخزينها في مكان ما لمزيد من المعالجة (على سبيل المثال ، في الذاكرة). وفقط بعد اكتمال القياسات ، يتم تحويل الببغاوات المجمعة ببطء إلى ثوانٍ
2. نانوثانية مطلوبة "على الطاير". على سبيل المثال ، تحتوي عملية القياس الخاصة بك على نوع من "المستهلك" الذي لا تتحكم فيه والذي يتوقع وقتًا بتنسيق "بشري"

الحالة الأولى بسيطة ، والثانية - تتطلب الحيلة. يجب أن يكون التحويل فعالاً قدر الإمكان. إذا كانت تستهلك الكثير من الموارد ، يمكن أن تشوه إلى حد كبير عملية القياس. سنتحدث عن التحويل الفعال أدناه. هنا قمنا حتى الآن بتحديد هذه المشكلة والانتقال إلى مشكلة أخرى.

عدادات الطابع الزمني ليست بسيطة كما نود. في بعض البنى:

1. ليس من المضمون أن يتم تحديث TSC على تردد عال. إذا تم تحديث TSC ، على سبيل المثال ، بمجرد كل ميكروثانية ، فلن يكون من الممكن إصلاح النانو ثانية معه.
2. قد يختلف تكرار تحديث TSC بمرور الوقت
3. على وحدات المعالجة المركزية المختلفة الموجودة في النظام ، يمكن تحديث TSC بترددات مختلفة
4. قد يكون هناك تحول بين TSCs موقوتة على وحدات المعالجة المركزية المختلفة

هنا مثال يوضح المشكلة الأخيرة. لنفترض أن لدينا نظامًا يحتوي على وحدتي CPU: CPU1 و CPU2. افترض أن TSC على وحدة المعالجة المركزية الأولى وراء الثانية بواسطة عدد علامات التجزئة ، وهو ما يعادل 5 ثوان. افترض أيضًا أنه تم إطلاق تيار في النظام الذي يقيس وقت الحسابات ، وهو ما يقوم به هو نفسه. للقيام بذلك ، يقرأ الدفق أولاً قيمة TSC ، ثم يقوم بالحساب ، ثم يقرأ قيمة TSC الثانية. إذا بقي مؤشر الترابط طوال حياته على وحدة معالجة مركزية واحدة فقط - على أي - فلا توجد مشاكل. ولكن ماذا لو بدأ مؤشر الترابط على CPU1 ، وقياس قيمة TSC الأولى هناك ، ثم في منتصف الحسابات تم نقله بواسطة نظام التشغيل إلى CPU2 ، حيث قرأ قيمة TSC الثانية؟ في هذه الحالة ، ستبدو الحسابات أطول بخمس ثوانٍ مما هي عليه بالفعل.

نظرًا للمشكلات المذكورة أعلاه ، لا يمكن لـ TSC أن يعمل كمصدر موثوق للوقت في بعض الأنظمة. ومع ذلك ، في أنظمة أخرى "تعاني" من نفس المشاكل ، لا يزال من الممكن استخدام TSC. أصبح ذلك ممكناً بفضل الميزات المعمارية الخاصة:

1. يمكن للجهاز توليد مقاطعة خاصة في كل مرة يتغير فيها التردد الذي يتم فيه تحديث TSC. في نفس الوقت ، توفر المعدات الفرصة لمعرفة التردد الحالي. بدلاً من ذلك ، يمكن وضع معدل تحديث TSC تحت سيطرة نظام التشغيل (راجع "Power ISA الإصدار 2.06 المراجعة B ، الكتاب الثاني ، الفصل 5")
2. إلى جانب قيمة TSC ، يمكن للجهاز أيضًا توفير معرف وحدة المعالجة المركزية التي تتم قراءة هذه القيمة عليها (راجع تعليمات Intel RDTSCP ، "دليل مطوري برامج Intel 64 و IA-32 للمعماريين" ، المجلد 2)
3. في بعض الأنظمة ، يمكنك ضبط قيمة TSC لكل وحدة معالجة مركزية (انظر تعليمات Intel WRMSR وتسجيل IA32_TIME_STAMP_COUNTER ، "دليل مطوري برامج Intel 64 و IA-32 للمعماريين" ، المجلد 3)

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

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

1. يقوم برنامج TSC بتحديد نفس التردد على كل وحدة معالجة مركزية في النظام
2. لا يتغير هذا التردد في الوقت المناسب
3. لا يوجد تحول بين TSCs موقوتة على وحدات المعالجة المركزية المختلفة

عند تصميم مكتبتي ، قررت المضي قدمًا من هذه الفرضية ، وليس من خلوص تطبيقات الأجهزة.

المكتبة

لم أبدأ في وضع شرائح الأجهزة لمجموعة من الهياكل المختلفة. بدلاً من ذلك ، قررت أن مكتبتي ستكون موجهة نحو الاتجاه. لديها تركيز تجريبي بحت:

1. يسمح بالتحقق التجريبي من موثوقية TSC كمصدر زمني
2. يسمح لك أيضًا بحساب المعلمات المطلوبة تجريبيًا لتحويل القراد بسرعة إلى نانو ثانية
3. بطبيعة الحال ، توفر المكتبة واجهات ملائمة لقراءة TSC وتحويل القراد إلى نانو ثانية "على الطاير"

كود المكتبة متاح هنا. سيتم تجميعه وتنفيذه فقط على Linux.

في الكود ، يمكنك الاطلاع على تفاصيل تنفيذ جميع الطرق ، والتي سيتم مناقشتها لاحقًا.

تقييم موثوقية TSC

توفر المكتبة واجهة تعيد تصنيفين:

1. أقصى تحول بين العدادات التي تنتمي إلى وحدات المعالجة المركزية المختلفة. تعتبر وحدات المعالجة المركزية المتاحة للعملية فقط. على سبيل المثال ، إذا كانت العملية تحتوي على ثلاثة وحدات معالجة مركزية متاحة ، وفي نفس الوقت يكون TSC على وحدات المعالجة المركزية هذه 50 ، 150 ، 20 ، فإن الحد الأقصى للتحول سيكون 150-20 = 130. بطبيعة الحال ، لن تتمكن المكتبة من الحصول على نقلة حقيقية حقيقية تجريبيًا ، ولكنها ستعطي تقديرًا يناسب هذا التحول. ماذا تفعل بعد ذلك مع التقييم؟ كيف تستعمل؟ هذا يحل بالفعل رمز العميل. لكن المعنى هو تقريبا ما يلي. الحد الأقصى للتحول هو القيمة القصوى التي يمكن من خلالها تشويه البعد الذي يقوم به رمز العميل. لنفترض ، في مثالنا مع ثلاثة وحدات معالجة مركزية ، أن كود العميل بدأ في قياس الوقت على CPU3 (حيث كان TSC 20) ، وانتهى على CPU2 (حيث كان TSC 150). اتضح أن 130 علامة إضافية سوف تتسلل إلى الفترة الزمنية المقاسة. وأبدا مرة أخرى. الفرق بين CPU1 و CPU2 سيكون 100 علامة فقط. بعد تقدير 130 علامة (في الواقع ، سيكون أكثر تحفظًا) ، يمكن للعميل أن يقرر ما إذا كانت قيمة التشويه هذه تناسبه أم لا
2. هل قيم TSC تقاس بالتسلسل على نفس أو زيادة وحدات المعالجة المركزية المختلفة. ها هي الفكرة. لنفترض أن لدينا العديد من وحدات المعالجة المركزية. افترض أن ساعتهم متزامنة وتدق في نفس التردد. ثم إذا قمت بقياس الوقت لأول مرة على وحدة معالجة مركزية واحدة ، ثم قم بقياسها مرة أخرى - بالفعل على أي من وحدات المعالجة المركزية المتاحة - فيجب أن يكون الرقم الثاني أكبر من الرقم الأول.
   
   سأدعو هذا التقدير أدناه تقدير رتابة TSC
   

الآن دعونا نرى كيف يمكننا الحصول على التقدير الأول:

1. أحد المعالجات المتاحة للعملية "أساسي"
2. ثم يتم فرز جميع وحدات المعالجة المركزية الأخرى ، ويتم حساب التحول لكل منها: TSC___CPU – TSC___CPU . يتم ذلك على النحو التالي:
   
   • أ) يتم أخذ ثلاث قيم مقاسة بالتسلسل (واحدة تلو الأخرى!): TSC_base_1, TSC_current, TSC_base_2 . هنا ، يشير التيار إلى أن القيمة تم قياسها على وحدة المعالجة المركزية الحالية ، والقاعدة على القاعدة
   • ب) يجب أن يكون التحول TSC___CPU – TSC___CPU في الفاصل الزمني [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . هذا على افتراض أن TSC تدق على نفس التردد على كل من وحدات المعالجة المركزية.
   • ج) يتم تكرار الخطوات أ) -ب) عدة مرات. يتم حساب تقاطع جميع الفواصل الزمنية التي تم الحصول عليها في الخطوة ب). يؤخذ الفاصل الزمني الناتج TSC___CPU – TSC___CPU للتحول TSC___CPU – TSC___CPU
   
   
3. بعد الحصول على تقدير التحول لكل وحدة معالجة مركزية بالنسبة للقاعدة ، من السهل الحصول على تقدير لأقصى تحول بين جميع وحدات المعالجة المركزية المتاحة:
   
   • أ) يتم حساب الحد الأدنى للفاصل الزمني ، والذي يشمل جميع الفترات الناتجة الناتجة في الخطوة 2
   • ب) يؤخذ عرض هذا الفاصل الزمني لتقدير الحد الأقصى للتحول بين TSC موقوتة على وحدات المعالجة المركزية المختلفة
   
   

لتقييم الرتابة في المكتبة ، يتم تنفيذ الخوارزمية التالية:

1. لنفترض أن العملية تحتوي على N CPU متاحة
2. قياس TSC على CPU1
3. قياس TSC على CPU2
4. ...
5. قياس TSC على CPUN
6. قياس TSC مرة أخرى على CPU1
7. نتحقق من أن القيم المقاسة تزداد بشكل رتيب من الأول إلى الأخير

من المهم هنا أن يتم قياس القيمتين الأولى والأخيرة على نفس وحدة المعالجة المركزية. وها هو السبب. لنفترض أن لدينا 3 وحدات معالجة مركزية. افترض أن TSC على CPU2 قد تم إزالته بواسطة +100 من العلامات النسبية لـ TSC على CPU1. افترض أيضًا أن TSC على CPU3 يتم إزالته بواسطة +100 علامة نسبة إلى TSC على CPU2. تأمل سلسلة الأحداث التالية:

• اقرأ TSC على CPU1. فليحصل على قيمة 10
• مرت 2 القراد
• قراءة TSC على CPU2. يجب أن يكون 112
• مرت 2 القراد
• قراءة TSC على CPU3. يجب أن يكون 214

حتى الآن ، تبدو الساعة متزامنة. ولكن دعنا نقيس TSC على CPU1 مرة أخرى:

• مرت 2 القراد
• اقرأ TSC على CPU1. يجب أن يكون 16

عفوًا! تمزق الرتابة. اتضح أن قياس القيم الأولى والأخيرة على نفس وحدة المعالجة المركزية يسمح لك باكتشاف التحولات الكبيرة أكثر أو أقل بين الساعات. السؤال التالي بالطبع: "ما حجم التحولات؟" يعتمد مقدار التحول الذي يمكن اكتشافه على الوقت المنقضي بين قياسات TSC المتتالية. في المثال المحدد ، هذه ليست سوى 2 علامات. سيتم الكشف عن التحولات بين ساعات تتجاوز 2 القراد. بشكل عام ، لن يتم الكشف عن التحولات التي تقل عن الوقت المنقضي بين القياسات المتعاقبة. لذلك ، كلما كانت القياسات أكثر كثافة في الوقت المناسب ، كان ذلك أفضل. تعتمد دقة كلا التقديرات على هذا. كلما كانت القياسات أكثر كثافة:

• كلما انخفض تقدير التحول الأقصى
• كلما زادت الثقة في تقييم الرتابة

في القسم التالي ، سنتحدث عن كيفية أخذ قياسات ضيقة. سأضيف هنا أنه أثناء حساب تقديرات موثوقية TSC ، تقوم المكتبة بإجراء العديد من عمليات الفحص "القمل" الأكثر بساطة ، على سبيل المثال:

• التحقق المحدود من أن TSCs على وحدات المعالجة المركزية المختلفة تدق بنفس السرعة
• التحقق من أن العدادات تتغير حقًا بمرور الوقت ، وليس فقط إظهار القيمة نفسها

طريقتان لجمع قيم العداد

في المكتبة ، طبقت طريقتين لجمع قيم TSC:

1. التبديل بين وحدة المعالجة المركزية . في هذه الطريقة ، يتم جمع جميع البيانات اللازمة لتقييم موثوقية TSC بواسطة خيط واحد "يقفز" من وحدة المعالجة المركزية إلى أخرى. كلتا الخوارزميتين الموصوفتين في القسم السابق مناسبتان لهذه الطريقة وغير مناسبتين للآخر.
   "التبديل بين وحدة المعالجة المركزية" ليس له استخدام عملي. تم تنفيذ الطريقة فقط من أجل "اللعب". تكمن المشكلة في الطريقة في أن الوقت المطلوب "لسحب" دفق من وحدة معالجة مركزية إلى أخرى كبير جدًا. وفقًا لذلك ، يمر الكثير من الوقت بين قياسات TSC المتتالية ، ودقة التقديرات منخفضة جدًا. على سبيل المثال ، يتم الحصول على تقدير نموذجي للتحول الأقصى بين TSC في منطقة 23000 علامة.
   
   ومع ذلك ، فإن الطريقة لها ميزتان:
   
   • أنها حتمية تماما. إذا كنت بحاجة إلى قياس TSC بالتتابع على CPU1 ، CPU2 ، CPU3 ، فإننا نأخذها ونفعلها: قم بالتبديل إلى CPU1 ، اقرأ TSC ، انتقل إلى CPU2 ، اقرأ TSC ، وأخيرًا ، انتقل إلى CPU3 ، اقرأ TSC
   • من المفترض ، إذا كان عدد وحدات المعالجة المركزية في النظام ينمو بسرعة كبيرة ، فيجب أن ينمو وقت التبديل بينها بشكل أبطأ بكثير. لذلك ، نظريًا ، على ما يبدو ، يمكن أن يوجد نظام - نظام كبير جدًا! - يتم فيه تبرير استخدام الطريقة. ولكن لا يزال هذا غير مرجح
   
   
2. القياسات المطلوبة باستخدام CAS . في هذه الطريقة ، يتم جمع البيانات بالتوازي من خلال مؤشرات ترابط متعددة. يبدأ كل وحدة المعالجة المركزية المتوفرة مؤشر ترابط واحد. يتم ترتيب القياسات التي يتم إجراؤها بواسطة خيوط مختلفة في تسلسل واحد باستخدام عملية "المقارنة والتبديل". يوجد أدناه جزء من الكود يوضح كيفية القيام بذلك.
   تم استعارة فكرة الطريقة من fio ، وهي أداة شائعة لتوليد أحمال الإدخال / الإخراج.
   
   تبدو تقديرات الموثوقية التي تم الحصول عليها باستخدام هذه الطريقة جيدة بالفعل. على سبيل المثال ، تم بالفعل الحصول على تقدير للحد الأقصى للتحول على مستوى عدة مئات من القراد. يتيح لك فحص الرتابة التقاط الساعة خارج المزامنة ضمن مئات العلامات.
   
   ومع ذلك ، فإن الخوارزميات الواردة في القسم السابق ليست مناسبة لهذه الطريقة. من المهم بالنسبة لهم أن يتم قياس قيم TSC بترتيب محدد مسبقًا. طريقة "القياسات التي طلبتها CAS" لا تسمح بذلك. بدلاً من ذلك ، يتم أولاً جمع سلسلة طويلة من القياسات العشوائية ، ثم تحاول الخوارزميات (المختلفة بالفعل) العثور على القيم المقروءة على وحدات المعالجة المركزية "المناسبة" في هذا التسلسل.
   
   لن أعطي هذه الخوارزميات هنا ، حتى لا تسيء انتباهك. يمكنك رؤيتها في الكود. هناك العديد من التعليقات. من الناحية النظرية ، هذه الخوارزميات هي نفسها. نقطة جديدة في الأساس هي التحقق من كيفية أن تكون تسلسلات TSC المكتوبة عشوائيًا "نوعية" إحصائيًا. من الممكن أيضًا تحديد الحد الأدنى المقبول من الأهمية الإحصائية لتقديرات موثوقية TSC.
   
   نظريًا ، في الأنظمة الكبيرة جدًا ، يمكن أن تعطي طريقة "طلب CAS" نتائج ضعيفة. تتطلب الطريقة معالجات للتنافس للوصول إلى موقع ذاكرة مشترك. إذا كان هناك الكثير من المعالجات ، يمكن أن تصبح المنافسة شديدة للغاية. ونتيجة لذلك ، سيكون من الصعب إنشاء تسلسل قياس بخصائص إحصائية جيدة. ومع ذلك ، في الوقت الحالي ، يبدو هذا الوضع غير مرجح.
   

لقد وعدت بعض التعليمات البرمجية. إليك ما يبدو لبناء قياسات في سلسلة واحدة باستخدام CAS.

  for ( uint64_t i = 0; i < arg->probes_count; i++ ) { uint64_t seq_num = 0; uint64_t tsc_val = 0; do { __atomic_load( seq_counter, &seq_num, __ATOMIC_ACQUIRE); __sync_synchronize(); tsc_val = WTMLIB_GET_TSC(); } while ( !__atomic_compare_exchange_n( seq_counter, &seq_num, seq_num + 1, false, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)); arg->tsc_probes[i].seq_num = seq_num; arg->tsc_probes[i].tsc_val = tsc_val; } 

يتم تنفيذ هذا الرمز على كل وحدة المعالجة المركزية المتاحة. جميع المواضيع لديها حق الوصول إلى المتغير المشترك seq_counter . قبل قراءة TSC ، يقرأ الدفق قيمة هذا المتغير ويخزنه في المتغير seq_num . ثم يقرأ TSC. ثم تحاول زيادة seq_counter تلقائيًا بمقدار واحد ، ولكن فقط إذا لم تتغير قيمة المتغير منذ قراءته. إذا كانت العملية ناجحة ، فهذا يعني أن الخيط تمكن من " seq_num " على رقم التسلسل المخزن في seq_num خلف قيمة TSC المقاسة. الرقم التسلسلي التالي ، الذي سيكون قادرًا على التوقيع المساحي له (ربما في موضوع آخر) سيكون رقمًا آخر. لهذا الرقم مأخوذ من متغير seq_counter ، وكل استدعاء ناجح لـ __atomic_compare_exchange_n() يزيد هذا المتغير بمقدار واحد.


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

تحويل القراد إلى نانو ثانية على الطاير

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

سأبدأ بمثال.

من الناحية المثالية ، أود تحويل القراد إلى نانو ثانية مثل هذا:
ns_time = tsc_ticks / tsc_per_ns
نريد أن يكون الوقت المنقضي في التحويل ضئيلاً. لذلك ، نهدف إلى استخدام الحساب الصحيح بشكل حصري. دعونا نرى كيف يمكن أن يهددنا هذا.

إذا كانت tsc_per_ns = 3 ، فإن القسمة الصحيحة البسيطة ، من وجهة نظر الدقة ، تعمل بشكل جيد: ns_time = tsc_ticks / 3 .

ولكن ماذا لو tsc_per_ns = 3.333 ؟إذا تم تقريب هذا الرقم إلى 3 ، فستكون دقة التحويل منخفضة جدًا. للتغلب على هذه المشكلة على النحو التالي:
ns_time = (tsc_ticks * factor) / (3.333 * factor).

إذا كان العامل factorكبيرًا بما يكفي ، فستكون الدقة جيدة. لكن شيئًا سيبقى سيئًا. وهي التحويل الزائد. القسمة الصحيحة هي عملية مكلفة للغاية. على سبيل المثال ، في الإصدار x86 ، يتطلب الأمر 10 دورات ساعة. بالإضافة إلى ذلك ، لا يتم دائمًا تنفيذ عمليات القسمة الصحيحة.

نعيد كتابة صيغة لدينا في شكل يعادل
ns_time = (tsc_ticks * factor / 3.333) / factor.

القسم الأول ليس مشكلة. يمكننا إجراء حساب (factor / 3.333)مسبق. لكن الانقسام الثاني لا يزال الألم. للتخلص منها ، دعنا نختارfactorيساوي قوة اثنين. بعد ذلك ، يمكن استبدال القسم الثاني بتغيير صغير - عملية بسيطة وسريعة.

كيف يمكنك اختيار حجم كبير factor؟ لسوء الحظ ، factorلا يمكن أن يكون كبيرًا بشكل تعسفي. وهي محدودة بشرط ألا يؤدي الضرب في البسط إلى تجاوز نوع 64 بت. نعم ، نريد استخدام أنواع "أصلية" فقط. مرة أخرى ، للحفاظ على النفقات العامة للتحويل إلى الحد الأدنى.

لنر الآن كيف يمكن أن تكون كبيرة factorفي مثالنا المحدد. افترض أننا نريد العمل بفترات زمنية تصل إلى سنة واحدة. خلال العام، tiknet TSC الأوقات التالية: 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000. تقسيم قيمة الحد الأقصى من عدد من نوع 64 بت هي: 18446744073709551615 / 105109488000000000 ~ 175.5. لذا التعبير(factor / 3.333)لا يجب أن تكون أكثر من هذه القيمة. ثم لدينا factor <= 175.5 * 3.333 ~ 584.9. أكبر قوة لاثنين لا تتجاوز هذا الرقم هي 512. لذلك ، تأخذ صيغة التحويل لدينا الشكل:

ns_time = (tsc_ticks * 512 / 3.333) / 512

أو:

ns_time = tsc_ticks * 153 / 512

جيد. دعونا نرى الآن ما تحتويه هذه الصيغة بدقة. سنة واحدة تحتوي على 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000نانو ثانية. لدينا صيغة تعطي: 105109488000000000 * 153 / 512 = 31409671218750000. الفرق مع القيمة الحالية هو 126328781250000 نانو ثانية ، أو 126328781250000 / 1000000000 / 60 / 60 ~ 35ساعات.

هذا خطأ كبير. نريد دقة أفضل. ماذا لو قمنا بقياس فترات زمنية لا تزيد عن ساعة؟ سأحذف الحسابات. إنها مطابقة تمامًا لتلك التي تم القيام بها للتو. ستكون الصيغة النهائية:

ns_time = tsc_ticks * 1258417 / 4194304(1)

سيكون خطأ التحويل 119305 نانوثانية في الساعة الواحدة (وهو أقل من 0.2 مللي ثانية). جيد جدا. إذا كانت القيمة القصوى القابلة للتحويل أقل من ساعة ، فستكون الدقة أفضل. لكن كيف نستخدم هذا؟ لا تحدد القياسات الزمنية لساعة واحدة؟

دعونا ننتبه إلى اللحظة التالية:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

إذا قمنا بالحساب tsc_ticks_per_1_hour، فيمكننا الاستخراج number_of_hoursمنها tsc_ticks. بعد ذلك ، نعرف عدد النانو ثانية المتضمنة في ساعة واحدة. لذلك ، لن يكون من الصعب علينا أن نترجم بالثواني النانوية ذلك الجزء tsc_ticksالذي يتوافق مع عدد كامل من الساعات. لإكمال التحويل ، سنحتاج إلى الترجمة في نانو ثانيةtsc_ticks_remainder. ومع ذلك ، فإننا نعلم أن هذا العدد من القراد جاء في أقل من ساعة. لذا ، لتحويلها إلى نانو ثانية ، يمكننا استخدام الصيغة (1).

تم.آلية التحويل هذه تناسبنا. دعونا نلخصها ونحسنها الآن.

بادئ ذي بدء ، نريد أن يكون لدينا تحكم مرن في أخطاء التحويل. لا نريد ربط معلمات التحويل بفاصل زمني مدته ساعة واحدة. فليكن فاصل زمني تعسفي:

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

مرة أخرى ، تذكر كيفية تحويل الباقي إلى نانو ثانية:

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

احسب معلمات التحويل (نحن نعلم ذلك tsc_ticks_remainder < modulus): من أجل التعب ، تجدر الإشارة إلى أن عدم المساواة الأخير لا يعادل الأول في إطار الحساب الصحيح. لكنني لن أطيل في الحديث عن هذا لفترة طويلة. لا يسعني إلا أن أقول أن التفاوت الأخير أكثر حدة من الأول ، وبالتالي آمن للاستخدام. بمجرد الحصول عليها من التفاوت الأخير ، نحسب:

modulus * (factor / tsc_per_nsec) <= UINT64_MAX
factor <= (UINT64_MAX / modulus) * tsc_per_nsec
2 ^ shift <= (UINT64_MAX / modulus) * tsc_per_nsec




shift

factor = 2 ^ shift
mult = factor / tsc_per_nsec


ثم يتم استخدام هذه المعلمات لتحويل الباقي إلى نانو ثانية: لذا ، اكتشفنا تحويل الباقي. المشكلة القادمة التي يتعين حلها - هو إزالة و من . كالعادة ، نريد أن نفعل ذلك بسرعة. كالعادة ، لا نريد استخدام القسمة. لذلك ، نختار ببساطة يساوي قوة اثنين: ثم:

ns_per_remainder = (tsc_ticks_remainder * mult) >> shift


tsc_ticks_remaindernumber_of_moduli_periodstsc_ticksmodulus

modulus = 2 ^ remainder_bit_length



number_of_moduli_periods = tsc_ticks >> remainder_bit_length
tsc_ticks_remainder = tsc_ticks & (modulus - 1)

عظيم.نحن نعرف الآن كيفية الاستخراج من tsc_ticks number_of_moduli_periodsو tsc_ticks_remainder. ونعرف كيفية التحويل tsc_ticks_remainderإلى نانو ثانية. يبقى أن نفهم كيفية تحويل هذا الجزء من القراد ، الذي هو متعدد ، إلى نانو ثانية modulus. لكن كل شيء بسيط:

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulusيمكنك الحساب مقدمًا. علاوة على ذلك ، وفقًا لنفس الصيغة التي نحول بها الباقي. يمكن استخدام هذه الصيغة لفترات زمنية لم تعد modulus. نفسه modulus، بالطبع ، لم يعد modulus.

ns_per_modulus = (modulus * mult) >> shift

هذا كل شيء!تمكنا من حساب جميع المعلمات اللازمة لتحويل القراد إلى نانو ثانية على الطاير. الآن تلخيص إجراء التحويل بإيجاز:

1. لدينا tsc_ticks
2. number_of_moduli_periods = tsc_ticks >> remainder_bit_length
3. tsc_ticks_remainder = tsc_ticks & (modulus - 1)
4. ns = ns_per_modulus * number_of_moduli_periods + (tsc_ticks_remainder * mult) >> shift

في هذا الإجراء، المعلمات remainder_bit_length، modulus, ns_per_modulus، multو shiftتقدم precalculation.

إذا كنت لا تزال تقرأ هذا المنشور ، فأنت عظيم أو عظيم. من الممكن أن تكون محلل أداء أو مطورًا لبرامج عالية الأداء.

حتى هنا.اتضح أننا لم ننتهي بعد :)

تذكر كيف قمنا بحساب المعلمة mult؟ كان هكذا:

mult = factor / tsc_per_nsec

سؤال: من أين أتت tsc_per_nsec؟
عدد القراد في نانو ثانية هو قيمة صغيرة جدًا. في الواقع ، يتم tsc_per_nsecاستخدام مكتبتي بدلاً من ذلك (tsc_per_sec / 1000000000). هذا هو:

mult = factor * 1000000000 / tsc_per_sec

وهناك سؤالان مثيران للاهتمام:

1. لماذا tsc_per_secوليس tsc_per_msecعلى سبيل المثال؟
2. من أين تحصل على هذه tsc_per_sec؟

لنبدأ بالأول. يستخدم Fio الآن فعليًا عدد علامات التجزئة لكل مللي ثانية. وهناك مشاكل في ذلك. على الجهاز، المعلمات التي كنت المذكورين أعلاه tsc_per_msec = 2599998. بينما tsc_per_sec = 2599998971. إذا جلبنا هذه الأرقام إلى مقياس واحد ، فستكون نسبتها قريبة جدًا من الوحدة: 0.999999626. ولكن إذا استخدمنا الأول وليس الثاني ، فسيكون لدينا 374 خطأ نانو ثانية لكل ثانية. لذلك - tsc_per_sec.

أبعد ... كيف نحسب tsc_per_sec؟

يتم ذلك على أساس القياس المباشر: "بعض الوقت" هو معلمة قابلة للتكوين. يمكن أن تكون أكبر أو أصغر أو تساوي ثانية واحدة. لنفترض أنها نصف ثانية. تحمل المزيد من أن الفرق الحقيقي بين ، و كان يساوي 0.6 ثواني. ثم .

start_sytem_time = clock_gettime()
start_tsc = WTMLIB_GET_TSC()
-
end_system_time = clock_gettime()
end_tsc = WTMLIB_GET_TSC()


end_system_timestart_system_timetsc_per_sec = (end_tsc – start_tsc) / 0,6

تعتبر المكتبة عدة قيم بهذه الطريقة tsc_per_sec. وبعد ذلك ، باستخدام الطرق القياسية ، "تنظف" الضوضاء الضوئية وتتلقى قيمة واحدة tsc_per_secيمكن الوثوق بها.

الدائرة قياس الوقت أعلاه، فإن النظام هو المكالمات المهمة clock_gettime()و WTMLIB_GET_TSC(). من المهم WTMLIB_GET_TSC()أن يمر الوقت نفسه بين مكالمتين كما بين مكالمتين clock_gettime(). ثم سيكون من الممكن ربط وقت النظام بسهولة مع علامات TSC. ومن ثم يمكن اعتبار تناثر القيم tsc_per_secعشوائيًا حقًا. باستخدام مخطط القياس هذا ، tsc_per_secستنحرف القيم عن متوسط ​​القيمة في أي اتجاه بنفس الاحتمال. وسيكون من الممكن تطبيق طرق التصفية القياسية عليها.

الخلاصة

ربما هذا كل شيء.

لكن موضوع قياس الوقت الفعال لا يقتصر على ذلك. هناك العديد من الفروق الدقيقة. بالنسبة للمهتمين ، أقترح العمل بشكل مستقل على القضايا التالية:

• تخزين معلمات التحويل في ذاكرة التخزين المؤقت أو - أفضل - على التسجيلات
• ما هي الحدود التي يمكن تخفيضها modulus(وبالتالي زيادة دقة التحويل)؟
• كما رأينا ، فإن دقة التحويل لا تتأثر فقط modulus، ولكن أيضًا بحجم الفاصل الزمني ، والذي يرتبط بالقراد ( tsc_per_msecأو tsc_per_sec). كيفية موازنة تأثير كلا العاملين؟
• TSC في الجهاز الظاهري. هل يمكنني استخدامه؟
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

تسمح الطرق التي تمت مناقشتها في هذه المقالة بقياس وقت المقياس الثاني بدقة ترتيب عدة عشرات من النانو ثانية. هذه هي الدقة التي ألاحظها بالفعل عند استخدام مكتبتي.

ومن المثير للاهتمام ، أن منظمة fio ، التي اقترضت منها بعض الأساليب ، تفقد بالضبط 700-900 نانو ثانية على مقياس ثانٍ (وهناك ثلاثة أسباب لذلك). بالإضافة إلى ذلك ، يفقد في سرعة التحويل بسبب تخزين الوقت بتنسيق Linux القياسي. ومع ذلك ، فقد سارعت إلى طمأنة مشجعي نظام المعلومات. لقد أرسلت للمطورين وصفًا لجميع مشكلات التحويل التي اكتشفتها . يعمل الناس بالفعل ، وسوف يقومون بإصلاحه قريبًا.

أتمنى لك الكثير من النانو ثانية الممتعة!