هيرميس: تعيين المهام الأمثل من حيث الكمون للحوسبة المحمولة المحدودة الموارد

مع قدرة الأجهزة المحمولة المتزايدة على الاتصال بخوادم السحابة من أي مكان، يمكن للأجهزة المحدودة الموارد أداء تحميل المهام الحاسوبية إما لتوفير استهلاك الموارد المحلية أو لتحسين الأداء. من المهم إيجاد تعيينات مثلى للمهام على الأجهزة المحلية والبعيدة يمكن أن تأخذ في الاعتبار الملف الشخصي الخاص بالتطبيق، وتوافر الموارد الحاسوبية، وموصلية الرابط، وإيجاد توازن بين تكاليف استهلاك الطاقة للأجهزة المحمولة والكمون بالنسبة للتطبيقات الحساسة للتأخير. نصيغ مشكلة صعبة من نوع NP تهدف إلى تقليل الكمون للتطبيق مع تلبية قيود استخدام الموارد المقررة. مختلفًا عن معظم الأعمال القائمة التي تعتمد إما على حل البرمجة الصحيحة الكاملة، أو على استراتيجيات تقديرية لا تقدم ضمانات أداء نظرية، نقترح هيرميس، مخطط تقدير وقت متعدد الحدود جديد (FPTAS). نحدد لمجموعة فرعية من حالات المشكلة، حيث يمكن وصف رسومات مهام التطبيق كأشجار متسلسلة، يوفر هيرميس حلاً بكمون لا يزيد عن (1 + ε) مرة من الحد الأدنى مع تكبد تعقيد يكون متعدد الحدود في حجم المشكلة و1/ε. نقدم أيضًا خوارزمية على الإنترنت لتعلم البيئة الديناميكية المجهولة وضمان أن الفجوة في الأداء مقارنة بالاستراتيجية المثلى محدودة بدالة لوغاريتمية مع الوقت. يتم التقييم باستخدام مجموعة بيانات حقيقية تم جمعها من عدة اختبارات، ويظهر أن هيرميس يحسن الكمون بنسبة 16 في المئة مقارنة باستراتيجية تقديرية منشورة سابقًا ويزيد وقت حساب وحدة المعالجة المركزية بنسبة 0.4 في المئة فقط من الكمون الإجمالي.