ทำไม AI ของคุณถึงไม่ต้องใช้คลาวด์เพื่อทำงานเร็วขึ้นอีกต่อไป

ผู้แต่ง: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen บทคัดย่อ: การอนุมานโครงข่ายประสาทเทียมเชิงลึก (DNN) บนข้อมูลสตรีมมิ่งต้องใช้ทรัพยากรคอมพิวเตอร์เพื่อตอบสนองข้อกำหนดด้านปริมาณงานการอนุมาน อย่างไรก็ตาม แอปพลิเคชันการเรียนรู้เชิงลึกที่อ่อนไหวต่อความหน่วงแฝงและข้อมูลส่วนบุคคลไม่สามารถยอมรับการขนถ่ายการคำนวณไปยังคลาวด์ระยะไกลได้ เนื่องจากต้นทุนการส่งข้อมูลที่เกี่ยวข้องและการขาดความไว้วางใจในผู้ให้บริการคลาวด์บุคคลที่สาม ในบรรดาโซลูชันเพื่อเพิ่มประสิทธิภาพในขณะที่การคำนวณยังคงอยู่ในสภาพแวดล้อมที่จำกัด การเร่งด้วยฮาร์ดแวร์อาจเป็นภาระ และการเพิ่มประสิทธิภาพโมเดลต้องใช้ความพยายามในการออกแบบอย่างมาก ในขณะเดียวกันก็บั่นทอนความแม่นยำ การแบ่งพาร์ติชัน DNN เป็นแนวทางเสริมที่สาม ซึ่งประกอบด้วยการกระจายปริมาณงานการอนุมานไปบนอุปกรณ์เอดจ์หลายเครื่องที่มีอยู่ โดยคำนึงถึงคุณสมบัติเครือข่ายเอดจ์และโครงสร้าง DNN โดยมีวัตถุประสงค์เพื่อเพิ่มปริมาณงานการอนุมานให้สูงสุด (จำนวนการอนุมานต่อวินาที) กระดาษนำเสนอวิธีการคาดการณ์ความหน่วงแฝงในการอนุมานและการส่งข้อมูลสำหรับการปรับใช้ DNN แบบกระจายแบบหลายเธรด และกำหนดกระบวนการเพิ่มประสิทธิภาพเพื่อเพิ่มปริมาณงานการอนุมานให้สูงสุด จากนั้นนำเสนอและวิเคราะห์ตัวแก้แบบ branch and bound เพื่อวัดประสิทธิภาพและความซับซ้อนที่ได้รับ การวิเคราะห์นี้นำไปสู่การกำหนด "accelerator region" ซึ่งอธิบายเงื่อนไขที่แน่นอนเกี่ยวกับคุณสมบัติ DNN และเครือข่ายที่การแบ่งพาร์ติชัน DNN มีประโยชน์ สุดท้ายผลการทดลองยืนยันการจำลองและแสดงการปรับปรุงปริมาณงานการอนุมานในการปรับใช้เอดจ์ตัวอย่าง การแบ่งพาร์ติชัน DNN ที่เอดจ์ช่วยเร่งปริมาณงานการอนุมาน ในขณะที่ลดการใช้แบนด์วิดท์และความหน่วงแฝงไปยังเซิร์ฟเวอร์ส่วนกลาง เช่น ในคลาวด์ บทนำ ในปี 2020 อุปกรณ์ที่เชื่อมต่อกันสร้างข้อมูลประมาณ 2.5 ควินทิลเลี่ยนไบต์ต่อวัน ในบริบทนี้ ปัญญาประดิษฐ์ (AI) เป็นหนึ่งในเทคโนโลยีที่สามารถจัดการกับปริมาณข้อมูลที่ผลิตเพิ่มขึ้นอย่างต่อเนื่องได้ดีที่สุด ในหลากหลายสาขา เช่น การตรวจจับวัตถุในคอมพิวเตอร์วิทัศน์ การจดจำใบหน้า การรู้จำเสียง การประมวลผลภาษาธรรมชาติ หรือการขับขี่อัตโนมัติ AI และโดยเฉพาะอย่างยิ่ง Deep Learning (DL) นอกจากข้อมูลจำนวนมากแล้ว ยังต้องการความสามารถที่สำคัญในด้านพลังการประมวลผลและหน่วยความจำ ซึ่งทำให้การประมวลผลแบบคลาวด์เป็นโซลูชันโฮสติ้งสำหรับปริมาณงาน AI ที่เป็นค่าเริ่มต้น ดังนั้น ในปี 2019 งาน AI 96% ถูกรันบนคลาวด์ แอปพลิเคชัน AI อาจมีข้อจำกัดด้านความหน่วงแฝงที่เข้มงวด เช่น ในการขับขี่อัตโนมัติ การตรวจสอบการผลิต หรือการอนุมานแบบเรียลไทม์ใดๆ ที่เกี่ยวข้องกับการโต้ตอบกับโลกแห่งความเป็นจริง ตัวอย่างเช่น การตอบสนองเฉลี่ยในการขับขี่อัตโนมัติต้องน้อยกว่า 100 มิลลิวินาที ทำให้เวลาเดินทางไปกลับไปยังคลาวด์นานเกินไปสำหรับแอปพลิเคชันดังกล่าว ในทำนองเดียวกัน แอปพลิเคชันบางอย่างอาจสร้างการใช้งานลิงก์ที่สำคัญบนเครือข่าย เช่น ในกรณีของการประมวลผลวิดีโอคุณภาพสูงในคอมพิวเตอร์วิทัศน์ ซึ่งป้องกันไม่ให้แอปพลิเคชันเหล่านี้ทำงานบนคลาวด์ นโยบายความเป็นส่วนตัวของข้อมูลหรือกฎระเบียบการคุ้มครองข้อมูลอาจห้ามข้อมูลออกนอกสภาพแวดล้อมเฉพาะ สิ่งนี้ส่งเสริมการปรับใช้ AI ใน Edge Computing ซึ่งประกอบด้วยการย้ายงานการคำนวณจากศูนย์ข้อมูลให้ใกล้กับอุปกรณ์เอดจ์มากขึ้น หรือในบริเวณใกล้เคียงกับแหล่งข้อมูล เมื่อเทียบกับคลาวด์สาธารณะ เอดจ์เป็นสภาพแวดล้อมที่มีทรัพยากรจำกัดและมีข้อจำกัดที่สำคัญ ดังนั้น การพัฒนา AI สำหรับเอดจ์จึงแตกต่างจากการพัฒนา AI สำหรับคลาวด์โดยเนื้อแท้ การวิเคราะห์ข้อมูลใกล้กับแหล่งกำเนิดอาจเป็นเรื่องท้าทายเนื่องจากความจุของอุปกรณ์ที่ต่ำกว่า ความไม่ยืดหยุ่นของทรัพยากรที่มีอยู่ และความหลากหลายของเครือข่ายเอดจ์ ความจุการประมวลผลที่ลดลงหมายถึงปริมาณงานการอนุมานที่ทำได้ลดลง ทำให้การย้ายปริมาณงานที่หนักจากคลาวด์ไปยังเอดจ์ซับซ้อนยิ่งขึ้น ในบางแอปพลิเคชัน ปริมาณงานการอนุมาน หรือจำนวนการอนุมานต่อวินาทีที่สามารถทำได้ของ DNN สามารถเชื่อมโยงกับความแม่นยำของ DNN ได้ เช่น การติดตามวัตถุในสตรีมวิดีโอ ซึ่งการลดอัตราการอนุมานจาก 15 เป็น 5 การอนุมานต่อวินาที แสดงให้เห็นว่าคะแนน F1 ของตัวตรวจจับวัตถุ ลดลง 10% กล่าวอีกนัยหนึ่ง การปรับใช้ที่มีปริมาณงานการอนุมานต่ำอาจทำให้ข้อมูลสูญหายอย่างรุนแรง เช่น การตรวจจับที่สูญหายในแอปพลิเคชันการเฝ้าระวังวิดีโอ มีสองวิธีหลักที่มีอยู่เพื่อให้ตรงตามข้อกำหนดด้านประสิทธิภาพบนเครือข่ายเอดจ์ที่จำกัด: การบีบอัดโมเดล หรือการเร่งด้วยฮาร์ดแวร์ *การบีบอัดโมเดล* ประกอบด้วยการลดและเพิ่มประสิทธิภาพโครงข่ายประสาทเทียมให้เป็นเวอร์ชันที่มีน้ำหนักเบา ซึ่งมักจะทำงานได้ไม่ดีนักของโมเดล วิธีการบีบอัดโมเดลมาตรฐาน ได้แก่ การตัดแต่งกิ่ง (pruning) คือการลบพารามิเตอร์ที่ไม่จำเป็นในโมเดล การควอนไทซ์ (quantization) คือการลดหน่วยความจำที่จัดสรรไว้เพื่อจัดเก็บโมเดล และการกลั่นความรู้ (knowledge distillation) คือการฝึกโครงข่ายประสาทเทียมที่เล็กกว่าด้วยความรู้ที่สกัดมาจากโมเดลที่ใหญ่กว่า การเพิ่มประสิทธิภาพโมเดลต้องใช้ความพยายามในการออกแบบอย่างมากและอาจเป็นอุปสรรคต่อความแม่นยำของโมเดล *การเร่งด้วยฮาร์ดแวร์* บนอุปกรณ์เอดจ์หมายถึงการค้นหาฮาร์ดแวร์ที่สามารถประหยัดพลังงานและมีน้ำหนักเบา ในขณะที่ยังคงสามารถดำเนินการอนุมานด้วยประสิทธิภาพที่เพียงพอ มีฮาร์ดแวร์หลายประเภทสำหรับการเร่งที่เอดจ์ ซึ่งแตกต่างกันไปในด้านประสิทธิภาพและความจำเพาะ แต่หน่วยประมวลผลมาตรฐานไม่สามารถตอบสนองความคาดหวังได้ และฮาร์ดแวร์เฉพาะ เช่น ASIC พบว่าไม่สามารถปฏิบัติได้จริงและมีราคาแพง การแบ่งพาร์ติชัน DNN เป็นวิธีการเสริมสำหรับการเร่งการอนุมานโดยใช้ประโยชน์จากอุปกรณ์ที่มีอยู่จำนวนมากในเครือข่ายเอดจ์เพื่อกระจายการคำนวณการอนุมาน ซึ่งสามารถใช้เพียงอย่างเดียว หรือร่วมกับอีกสองวิธี การแบ่งพาร์ติชัน DNN ประกอบด้วยการพิจารณาโครงข่ายประสาทเทียมเป็นไปป์ไลน์เพื่อแบ่งออกเป็นพาร์ติชัน และกระจายพาร์ติชันเหล่านี้ไปยังอุปกรณ์เอดจ์ การวางพาร์ติชันเหล่านี้จะขึ้นอยู่กับทั้ง DNN และลักษณะเครือข่ายพื้นฐาน การแบ่งพาร์ติชัน DNN อาศัยการระบุจุดแบ่ง (split points) ซึ่งเป็นจุดในกราฟโมเดลที่โมเดลถูกแยกออกเป็นพาร์ติชัน ในระหว่างการทำงาน พาร์ติชันจะถูกรันตามลำดับ โดยแต่ละพาร์ติชันจะส่งผลการอนุมานระดับกลางไปยังพาร์ติชันถัดไป สิ่งนี้ช่วยให้แต่ละพาร์ติชันสามารถเริ่มประมวลผลข้อมูลอินพุตถัดไป ในขณะที่อุปกรณ์อื่นๆ ยังคงประมวลผลข้อมูลที่ถูกขนถ่ายออกไป ซึ่งช่วยเพิ่มปริมาณงานการอนุมาน ดังแสดงในรูปที่ 1 ในส่วนที่เหลือของเอกสารนี้ การแบ่งพาร์ติชัน DNN จะแสดงผ่านตัวอย่างการอนุมานแบบเรียลไทม์บนสตรีมวิดีโอ A. งานที่เกี่ยวข้อง วิธีการแบ่งพาร์ติชัน DNN ที่ได้มาจากการขนถ่ายข้อมูลจากโมบายล์เอดจ์สู่คลาวด์ (mobile edge-cloud offloading) พยายามเพิ่มประสิทธิภาพตัวชี้วัดประสิทธิภาพต่างๆ เช่น ความหน่วงแฝงในการคำนวณ การใช้พลังงาน การใช้ทรัพยากร ต้นทุน หรือปริมาณงาน การแบ่งพาร์ติชัน DNN อาศัยการเชื่อมโยงเมตริกเหล่านี้อย่างน้อยหนึ่งเมตริกเพื่อกำหนดเป้าหมายการเพิ่มประสิทธิภาพ และวิธีการที่ใช้ประโยชน์จากเมตริกนี้เพื่อค้นหารูปแบบการแบ่งพาร์ติชัน ตัวอย่างเช่น Neurosurgeon ค้นหาจุดแบ่งเดียว โดยเก็บพาร์ติชันแรกไว้ที่เอดจ์และขนถ่ายพาร์ติชันที่สองไปยังคลาวด์ เพื่อลดความหน่วงแฝงและการใช้พลังงาน แอปพลิเคชันใน IoT ยังได้พิจารณาการแบ่งพาร์ติชันและการขนถ่าย DNN หลายรายการร่วมกันเพื่อเพิ่มประสิทธิภาพพลังงาน ความล่าช้า และ/หรือต้นทุน โดยใช้ตัวแก้ปัญหาต่างๆ เช่น SPSO-GA ที่รวม Particle Swarm Optimization (PSO) และ Genetics Algorithm (GA) หรือ DDPQN ซึ่งใช้ Deep Reinforcement Learning เพื่อค้นหารูปแบบการแบ่งพาร์ติชัน ตัวอย่างอื่นๆ ได้แก่ DINA ซึ่งกำหนดปัญหา Integer Non Linear Programming (INLP) และใช้ตัวแก้ปัญหาที่ใช้ทฤษฎีการจับคู่ เพื่อเพิ่มประสิทธิภาพความล่าช้าและการใช้ทรัพยากรในเครือข่ายหมอก (fog networks) วิธีการเพิ่มประสิทธิภาพปริมาณงานการอนุมาน ได้แก่ DNN surgery ซึ่งใช้ขนาดที่เล็กกว่าของผลลัพธ์เลเยอร์ DNN ระดับกลางเพื่อแบ่งการคำนวณการอนุมานระหว่างเอดจ์และคลาวด์ อัลกอริทึมทั้งสองสร้างสองพาร์ติชัน หนึ่งที่เอดจ์และอีกอันในคลาวด์ การศึกษาอื่นๆ ในสาขา mobile edge-cloud ยังรวมถึงการคำนวณแบบหลายเธรดในคลาวด์เพื่อเร่งปริมาณงานการอนุมานโดยรวมให้เร็วขึ้น การพึ่งพาคลาวด์สำหรับการคำนวณการอนุมานพาร์ติชันที่สองสันนิษฐานว่ามีการเชื่อมต่อเครือข่ายที่ดี ซึ่งอาจไม่แน่นอนกับการเชื่อมต่อที่ไม่ดีของบางการปรับใช้เอดจ์ที่แยกจากกัน Edgent ปรับวิธีการก่อนหน้านี้ให้เข้ากับอุปกรณ์พกพาและเซิร์ฟเวอร์เอดจ์ที่มีอยู่ โดยผ่อนคลายข้อจำกัดในการขนถ่ายไปยังคลาวด์ วิธีการนี้เชื่อมโยงกับการฝึกอบรมและสถาปัตยกรรมโมเดลเฉพาะ และยังคงจำกัดการแบ่งพาร์ติชันไว้ที่สองพาร์ติชัน วิธีการอื่นๆ ได้พิจารณาจุดแบ่งหลายจุด เช่น IONN ซึ่งอธิบายปัญหาการแบ่งพาร์ติชันเพื่อลดความหน่วงแฝงและการใช้พลังงาน โดยคำนึงถึงเวลาในการอัปโหลดโมเดลไปยังเซิร์ฟเวอร์เอดจ์ด้วย วิธีการเหล่านี้มีปฏิสัมพันธ์กับคลาวด์ระยะไกล หรือจำกัดในลักษณะของการแบ่งพาร์ติชัน เช่น ต้องแบ่งออกเป็นสองส่วนพอดี โดยมีหรือไม่มีการทำงานแบบหลายเธรด ไม่มีงานวิจัยเกี่ยวกับการแบ่งพาร์ติชัน DNN ที่ระบุไว้พิจารณาทั้งจุดแบ่งหลายจุดและการทำงานแบบหลายเธรด B. การมีส่วนร่วม เอกสารฉบับนี้นำเสนอเฟรมเวิร์กการอนุมานแบบกระจายเพื่อเพิ่มปริมาณงานการอนุมานของการคำนวณ DNN แบบเรียลไทม์บนข้อมูลสตรีมมิ่ง ด้วยจุดแบ่งหลายจุดและการแบ่งพาร์ติชันแบบหลายเธรด การมีส่วนร่วมของเอกสารฉบับนี้มีดังนี้: แบบจำลองสำหรับการคำนวณและความหน่วงแฝงในการส่งข้อมูลของ DNN แบบกระจาย ซึ่งปริมาณงานการอนุมานที่คาดหวังของรูปแบบการแบ่งพาร์ติชันที่กำหนดสามารถประมาณได้ การกำหนดปัญหาการเพิ่มประสิทธิภาพสำหรับการแบ่งพาร์ติชัน DNN การนำตัวแก้ปัญหาแบบ branch and bound มาใช้สำหรับปัญหานี้ และการประเมินความซับซ้อน การจำลองเพื่อสำรวจการปรับปรุงประสิทธิภาพที่เป็นไปได้ด้วยคุณสมบัติเครือข่ายและ DNN ที่แตกต่างกัน การระบุพื้นที่ที่แน่นอนในคุณสมบัติเครือข่ายและ DNN ที่นำไปสู่การมีอยู่ของการแบ่งพาร์ติชันที่เหมาะสมที่สุด และต้นทุนในการคำนวณโซลูชันดังกล่าว หรือเงื่อนไขที่การแบ่งพาร์ติชัน DNN มีประโยชน์ ผลการทดลองที่แสดงพื้นที่ที่กำหนดในการจำลอง รวมถึงความแม่นยำของการคาดการณ์และอัตราเร่งปริมาณงานการอนุมานสุดท้ายสำหรับสภาพแวดล้อมแบบเอกพันธุ์และไม่เหมือนกัน สำหรับส่วนที่เหลือของเอกสารนี้ เพื่อหลีกเลี่ยงความสับสน โครงข่ายประสาทเทียมเชิงลึกที่แบ่งพาร์ติชันจะถูกอ้างถึงว่าเป็น *DNN* และคำว่า *เครือข่าย* จะหมายถึงเครือข่ายการสื่อสารทางกายภาพพื้นฐาน C. โครงร่างเอกสาร ส่วนที่เหลือของเอกสารนี้จัดเรียงดังนี้: ส่วนที่ II นำเสนอพื้นฐานของ Deep Learning และวิธีการแสดง DNN ในการศึกษานี้ ส่วนที่ III ให้รายละเอียดเกี่ยวกับวิธีการคาดการณ์ความหน่วงแฝงในการอนุมานและการส่งข้อมูลที่จำเป็นสำหรับส่วนที่ IV ซึ่งกำหนดปัญหาการเพิ่มประสิทธิภาพ รวมถึงอัลกอริทึม branch and bound เพื่อทำการตัดสินใจแบ่งพาร์ติชัน ส่วนที่ V นำเสนอผลการจำลองเพื่อวัดปริมาณประสิทธิภาพและความซับซ้อนของอัลกอริทึม branch and bound รวมถึงเงื่อนไขที่นำไปสู่การมีอยู่ของการแบ่งพาร์ติชันที่ปรับปรุงปริมาณงานการอนุมานในเครือข่ายเอกพันธุ์ ส่วนที่ VI นำเสนอผลการทดลองที่ยืนยันการจำลองในส่วนที่ V และแสดงการปรับปรุงปริมาณงานการอนุมานในการตั้งค่าทดลองแบบไม่เหมือนกัน สุดท้าย ส่วนที่ VII อภิปรายผลลัพธ์และขยายขอบเขตการใช้งานที่กว้างขึ้นของวิธีการนี้ ส่วนที่ II. พื้นฐาน: Deep Learning ภายในสาขา Machine Learning, Deep Learning (DL) หมายถึงวิธีการที่อาศัยการใช้ DNN หรือโครงข่ายประสาทเทียม (หรือวิธีการเรียนรู้ของเครื่องที่เกี่ยวข้อง) ที่มีชั้นซ่อนอยู่มากกว่าหนึ่งชั้น การอ้างอิงถึงสถาปัตยกรรม deep learning ยุคแรกสุดเผยแพร่ในปี 1967 แต่ก็ไม่ใช่จนกระทั่งปี 2010 ที่ DL ได้รับความนิยม ก่อนอื่นในการรู้จำเสียง จากนั้นในการตรวจจับวัตถุในภาพ เนื่องจากความสามารถในการจับความสัมพันธ์ที่ซับซ้อนในข้อมูลที่มีมิติสูง DL ถูกประมาณว่าคิดเป็นสัดส่วนส่วนใหญ่ของแอปพลิเคชัน AI ในปี 2022 โดยกว่า 75% ขององค์กรใช้ DNN สำหรับแอปพลิเคชันที่สามารถใช้วิธีการแบบคลาสสิกได้ วิธีการ DL ถูกกำหนดให้เป็น "เทคนิคสำหรับการเรียนรู้ของเครื่องที่สมมติฐานอยู่ในรูปแบบของวงจรพีชคณิตที่ซับซ้อนพร้อมความแข็งแกร่งในการเชื่อมต่อที่ปรับได้" วงจรพีชคณิตเหล่านี้มักจะจัดเป็นชั้นๆ ซึ่งเป็นขั้นตอนในการคำนวณ คำว่า *deep* หมายถึงอัลกอริทึมที่ประกอบด้วยชั้นมากกว่าหนึ่งชั้น มีโครงสร้าง DNN หลักสองประเภท: โครงข่ายประสาทเทียมแบบ feed-forward และโครงข่ายประสาทเทียมแบบ recurrent ทั้งสองประเภทของ DNN สามารถแสดงเป็นกราฟการคำนวณ โดยมีความแตกต่างหลักคือโครงข่ายประสาทเทียมแบบ feed-forward สามารถแสดงเป็นกราฟแบบไม่มีวัฏจักร (DAGs) ในขณะที่โครงข่ายประสาทเทียมแบบ recurrent อาจมีวัฏจักร โครงข่ายประสาทเทียมแบบ recurrent สร้างขึ้นสำหรับลำดับข้อมูล โดยที่แต่ละจุดข้อมูลมีความเป็นไปได้ที่จะขึ้นอยู่กับจุดข้อมูลก่อนหน้าในลำดับ ในขณะที่โครงข่ายประสาทเทียมแบบ feed-forward ไม่พิจารณาปฏิสัมพันธ์ระหว่างจุดต่างๆ ในลำดับข้อมูล สำหรับส่วนที่เหลือของเอกสารนี้ จะพิจารณากรณีของ DNN แบบ feed-forward ส่วนที่ III. การสร้างแบบจำลองการอนุมานแบบกระจาย ส่วนนี้จะนำเสนอแบบจำลองเพื่อแสดงคุณสมบัติ DNN และเครือข่ายเพื่อคาดการณ์ความหน่วงแฝงในการคำนวณ ความหน่วงแฝงในการส่งข้อมูล และปริมาณงานการอนุมานสุดท้ายของโซลูชันการแบ่งพาร์ติชันที่กำหนด A. การแสดง DNN และเครือข่าย DNN แบบ feed-forward ที่มี N ชั้น จะถูกสร้างแบบจำลองเป็น DAG GA=(L,E) โดยที่ L=(L1,…,LL) คือชั้นต่างๆ ของ DNN เส้นเชื่อม (Li,Lj)∈E คือการเชื่อมต่อระหว่างชั้น Li และ Lj แต่ละชั้น Li มีการใช้พลังงานในการคำนวณ ci ที่เกี่ยวข้อง ซึ่งวัดเป็นจำนวนการดำเนินการจุดลอยตัว (floating-point operations) ที่จำเป็นสำหรับการคำนวณ forward pass ผ่านชั้นนั้นๆ เส้นเชื่อม (Li,Lj) จะถูกกำหนดน้ำหนัก si,j ซึ่งสอดคล้องกับขนาดของข้อมูลที่ส่งผ่านระหว่างชั้น Li และ Lj เป็นไบต์ เครือข่ายทางกายภาพจะถูกสร้างแบบจำลองเป็นกราฟแบบเชื่อมต่อสมบูรณ์ G=(N,V) โดยที่ N=(N1,…,NN) คือชุดของโหนดการคำนวณ และ V คือชุดของลิงก์ระหว่างโหนด สมมติว่าโหนดการคำนวณ N1,…,NN มีอัตราการประมวลผล η1,…,ηN ตามลำดับ ซึ่งวัดเป็น floating-point operations ต่อวินาที สุดท้าย อัตราการส่งข้อมูลของลิงก์ระหว่างโหนดประชิด Na และ Nb จะถูกระบุเป็น θa,b ซึ่งวัดเป็นไบต์ต่อวินาที ทุกโหนด Ni จะเชื่อมต่อกับตัวเองด้วยอัตราการส่งข้อมูลอนันต์เพื่อแสดงถึงลิงก์ loopback และสมมติว่าลิงก์มีความสมมาตร คือ θa,b=θb,a การแบ่งพาร์ติชันจะถูกกำหนดเป็นฟังก์ชัน P:L→N หรือกล่าวคือ การแบ่งพาร์ติชันจะกำหนดหมายเลขโหนดให้กับแต่ละชั้นใน DNN สามารถอธิบายการแบ่งพาร์ติชันได้เป็นเมทริกซ์ P ขนาด (N×L) โดยที่ N คือจำนวนโหนดในเครือข่าย และ L คือจำนวนชั้นของ DNN และด้วย Pa,i=1 หากชั้น Li ถูกวางไว้บนโหนด Na และเป็น 0 หากไม่ ด้วยตัวอย่างที่แสดงในรูปที่ 2 ซึ่งมี L=7 ชั้น และ N=2 โหนดการคำนวณ การแบ่งพาร์ติชันที่แสดงด้วยชั้น {L1,L2,L3,L6,L7} บนโหนด N1 และชั้น {L4,L5} บนโหนด N2 จะแสดงดังนี้: เมื่อกำหนดรูปแบบการแบ่งพาร์ติชันแล้ว *เธรด* (thread) จะถูกกำหนดให้เป็นกลุ่มของชั้นที่เรียงต่อกันระหว่างจุดแบ่งสองจุด ซึ่งรันตามลำดับบนโหนดเดียวกัน ในตัวอย่างข้างต้น โหนด N1 จะรันสองเธรด เธรดแรกประกอบด้วยชั้น {L1,L2,L3} และเธรดที่สองประกอบด้วย {L6,L7} ด้วยสัญกรณ์ที่กำหนดเหล่านี้ ส่วนที่เหลือของส่วนนี้จะอนุพันธ์นิพจน์แบบปิดของปริมาณงานการอนุมานที่ได้รับจากการแบ่งพาร์ติชันที่กำหนด ซึ่งเป็นฟังก์ชันของความหน่วงแฝงในการอนุมาน (ส่วนที่ III-B) และความหน่วงแฝงในการส่งข้อมูล (ส่วนที่ III-C) B. การคาดการณ์ความหน่วงแฝงในการอนุมาน เมื่อกำหนดรูปแบบการแบ่งพาร์ติชัน ส่วนนี้จะพิจารณาการคาดการณ์ความหน่วงแฝงในการอนุมานบนโหนดที่แยกจากกัน ความหน่วงแฝงที่เกิดจากการคำนวณชั้น Li ที่มีการใช้พลังงาน ci ซึ่งจะคำนวณบนโหนด Na ที่มีอัตราการประมวลผล ηa จะแสดงเป็น Tci(Na)=ci/ηa เมื่อกำหนดชุดของชั้น L′⊂L ในทุกเธรดที่รันบนโหนด Na ที่มีอัตราการประมวลผล ηa ความหน่วงแฝงในการอนุมานสามารถแสดงได้เป็น: นิพจน์นี้เป็นการประมาณอันดับแรกของการประมาณความหน่วงแฝงในการอนุมาน โดยอิงจากจำนวน floating-point operations (FLOPs) ที่จำเป็นในการประมวลผล DNN หรือจำนวนการดำเนินการคูณ-บวกในโมเดล การประมาณความหน่วงแฝงในการอนุมานบนอุปกรณ์เอดจ์นั้นซับซ้อนเนื่องจากการเพิ่มประสิทธิภาพขณะทำงาน โซลูชันที่มีอยู่ เช่น nn-Meter คาดการณ์ความหน่วงแฝงในการอนุมานตาม FLOPs โซลูชันอื่นๆ อาศัยตารางค้นหาพร้อมเวลาอนุมานที่คำนวณไว้ล่วงหน้าสำหรับการอนุมานความหน่วงแฝง ตัวอย่างเช่น BRP-NAS ใช้กราฟคอนโวลูชันเน็ตเวิร์กที่ฝึกไว้ล่วงหน้าเพื่อคาดการณ์ความหน่วงแฝงในการอนุมาน ในขณะที่คำนึงถึงการเพิ่มประสิทธิภาพโมเดลขณะทำงาน ในสมการที่ 1 นอกจากนี้ยังสมมติว่าโปรเซสเซอร์ใช้ความจุเต็มที่ ซึ่งหมายความว่าโปรเซสเซอร์แบบหลายคอร์ถูกสร้างแบบจำลองเป็นโปรเซสเซอร์แบบแกนเดียวที่มีอัตราการประมวลผลเท่ากับผลรวมของอัตราการประมวลผลแกนของพวกมัน นอกจากนี้ยังสมมติว่าทรัพยากรการคำนวณถูกแบ่งปันอย่างเท่าเทียมกันระหว่างเธรด หรือโปรเซสเซอร์จัดสรรสัดส่วนเวลาเท่ากันให้กับแต่ละเธรด ทั่วทั้งโหนด เธรดที่มีความหน่วงแฝงสูงสุดจะเป็นตัวกำหนดปริมาณงานการอนุมานสำหรับ DNN แบบกระจาย หากไม่คำนึงถึงความหน่วงแฝงในการส่งข้อมูล ซึ่งหมายความว่าเมื่อเธรดที่จำกัดนี้คำนวณเฟรมข้อมูลเสร็จสิ้น มันจะเริ่มประมวลผลเฟรมถัดไปทันที เธรดอื่นๆ จะมีเวลาว่างก่อนที่จะประมวลผลเฟรมข้อมูลถัดไป เนื่องจากความหน่วงแฝงในการอนุมานของพวกมันต่ำกว่าความหน่วงแฝงสูงสุดนี้ ดังแสดงในรูปที่ 1 เมื่อกำหนดเมทริกซ์การแบ่งพาร์ติชัน P ความหน่วงแฝงในการอนุมานสามารถแสดงได้เป็นเวกเตอร์เดี่ยว Tc ขนาด N โดยที่ส่วนประกอบที่ a คือความหน่วงแฝงเธรดสูงสุดในการอนุมานบนโหนด Na หรือ Tca=Tc(Na): โดยที่ H คือเมทริกซ์แนวทแยงของอัตราการประมวลผลโหนดผกผัน (η−11,…,η−1N) และ c คือเวกเตอร์คอลัมน์ของการใช้พลังงานของแต่ละชั้น (c1,…,cL) C. การคาดการณ์ความหน่วงแฝงในการส่งข้อมูล ความหน่วงแฝงในการส่งข้อมูลสามารถคาดการณ์ได้ดังนี้: เวลาที่ใช้ในการส่งปริมาณข้อมูล si,j ระหว่างชั้น Li และ Lj บนลิงก์ (Na,Nb) ที่มีอัตราการส่งข้อมูลที่วัดได้ θa,b คือ Tti,j(Na,Nb)=si,j/θa,b เวลาในการดำเนินการถ่ายโอนข้อมูล si,j∈E′⊂E บนลิงก์ (Na,Nb) คือ: เช่นเดียวกับการคาดการณ์ความหน่วงแฝงในการอนุมาน สิ่งนี้หมายความว่าลิงก์จะถูกแบ่งปันอย่างเท่าเทียมกันระหว่างการถ่ายโอนข้อมูลจาก Na ไปยัง Nb การคาดการณ์ความหน่วงแฝงในการส่งข้อมูลอาศัยการประมาณอัตราการส่งข้อมูลของลิงก์ โดยเฉพาะอย่างยิ่ง *goodput* หรือปริมาณข้อมูลที่มีประโยชน์ที่ส่งต่อวินาที เช่นเดียวกับการประมาณความหน่วงแฝงในการอนุมาน นี่เป็นการประมาณอันดับแรก ซึ่งให้ผลการคาดการณ์ที่ดีได้อย่างมีประสิทธิภาพ ดังแสดงในรูปที่ 3 c ด้วยค่าสัมประสิทธิ์สหสัมพันธ์ R2=0.9998 ข้อเสียของวิธีนี้คือต้องใช้ลิงก์ให้เต็มประสิทธิภาพเพื่อรับการประมาณอัตราการส่งข้อมูล เมื่อกำหนดเมทริกซ์การแบ่งพาร์ติชัน P เมทริกซ์ความหน่วงแฝงในการส่งข้อมูล Tt สามารถกำหนดเป็นเมทริกซ์จัตุรัสขนาด L โดยที่ Tta,b=Tt(Na,Nb): โดยที่ ° คือผลคูณแบบเทอมต่อเทอม หรือ Hadamard product, Θ คือเมทริกซ์อัตราการส่งข้อมูลผกผัน หรือเมทริกซ์จัตุรัสขนาด N โดยที่ Θa,b=θ−1a,b และ S คือเมทริกซ์ขนาดการส่งข้อมูล หรือเมทริกซ์จัตุรัสขนาด L โดยที่ Si,j=si,j หาก Li ส่งข้อมูลไปยัง Lj และเป็น 0 หากไม่ ส่วนที่ IV. การแบ่งพาร์ติชัน DNN วัตถุประสงค์ของการแบ่งพาร์ติชัน DNN ในการศึกษานี้คือเพื่อเพิ่มปริมาณงานการอนุมานให้สูงสุด ซึ่งแสดงด้วย C ซึ่งสอดคล้องกับค่าผกผันของความหน่วงแฝงสูงสุดระหว่างความหน่วงแฝงในการคำนวณและการส่งข้อมูลทั้งหมด เมื่อกำหนดรูปแบบการแบ่งพาร์ติชัน P ปริมาณงานการอนุมานจะถูกกำหนดเป็น: การเพิ่มปริมาณงานการอนุมานให้สูงสุดเท่ากับการค้นหาค่า min-max ร่วมกันระหว่างเทอมทั้งหมดของ Tc และ Tt ซึ่งสามารถกำหนดเป็นปัญหาการเพิ่มประสิทธิภาพแบบไม่ต่อเนื่อง: โดยที่ Ji,j คือเมทริกซ์ที่ประกอบด้วยเลข 1 ทั้งหมดขนาด i×j เงื่อนไข (6) และ (7) กำหนดว่าแต่ละชั้นต้องถูกวางไว้บนโหนดเดียวเท่านั้น ปัญหานี้เป็นปัญหา Mixed Integer Non-linear Programming (MINLP) เมทริกซ์การแบ่งพาร์ติชันสามารถมองได้ว่าเป็นรูปแบบ one-hot encoded ของเวกเตอร์ขนาด (1×L) โดยมีค่าอยู่ใน [[1,N]] ปัญหามินlp นั้น NP-hard ซึ่งหมายความว่าความซับซ้อนในการค้นหาการแบ่งพาร์ติชัน DNN ที่เหมาะสมที่สุดคือ O(NL) เนื่องจากแต่ละชั้นใน L ชั้นสามารถวางไว้บน N โหนดได้ มีวิธีการฮิวริสติกหลายวิธีในการรับโซลูชันที่เหมาะสมที่สุดหรือใกล้เคียงที่สุดสำหรับปัญหานี้ในเวลาน้อยกว่าอัลกอริทึม brute force เช่น Genetic Algorithms (GA), Particle Swarm Optimization (PSO) หรือ Branch and Bound (B&B) วิธีการที่เลือกคือการนำ B&B มาปรับใช้ ซึ่งนำเสนอในส่วนที่ IV-A A. อัลกอริทึม Branch and Bound ส่วนนี้จะนำเสนอการปรับใช้ branch and bound (B&B) กับปัญหาการเพิ่มประสิทธิภาพการแบ่งพาร์ติชัน DNN ที่กำหนดในส่วนที่ IV ในอัลกอริทึม B&B พื้นที่โซลูชันจะแสดงด้วยต้นไม้ กระบวนการประกอบด้วยการกำจัดกิ่งทั้งหมดในต้นไม้ตามการประเมินคะแนนของโหนดราก สิ่งนี้บ่งชี้ถึงการมีอยู่ของโทโพโลยีต้นไม้ที่สร้างความสัมพันธ์ระหว่างคะแนนของโหนดในต้นไม้และขอบเขตของคะแนนของใบทั้งหมด การแสดงพื้นที่โซลูชันด้วยต้นไม้นี้เอื้อต่อการใช้อัลกอริทึม B&B ในการศึกษานี้ สมมติว่า ps เป็นรายการย่อยที่มีขนาด s ลูกของโหนด ps ในโทโพโลยีต้นไม้คือรายการทั้งหมดที่ขึ้นต้นด้วย ps หรือกล่าวคือ การแบ่งพาร์ติชันทั้งหมดที่ชั้น s แรกถูกวางตาม ps โหนดใบด้านล่าง ps ที่สอดคล้องกับ ps ที่เติมด้วยค่าสุดท้ายของ ps จะถูกติดป้าย ps~ ตัวอย่างเช่น หาก L=5 และ p2=(2,1) ดังนั้น p2~=(2,1,1,1,1) เมื่อกำหนด Ttmax=maxTt(ps~) ค่าสูงสุดของเมทริกซ์ความหน่วงแฝงในการส่งข้อมูลสำหรับการแบ่งพาร์ติชัน ps~ โหนดใบทั้งหมด p ด้านล่าง ps จะมีความหน่วงแฝงในการส่งข้อมูลสูงสุดสูงกว่า ps~ หรือ ∀p,maxTt(p)≥Ttmax สิ่งนี้อธิบายได้ว่าเนื่องจากเมื่อกำหนดการแบ่งพาร์ติชันย่อย การย้ายข้อมูลในชั้นที่เหลือใดๆ จะเพิ่มการถ่ายโอนข้อมูลระหว่างโหนดเท่านั้น ในระหว่างกระบวนการค้นหาการแบ่งพาร์ติชันที่เหมาะสมที่สุด p ซึ่งเพิ่มปริมาณงานการอนุมาน C(p,GA,GN) ให้สูงสุด และเมื่อกำหนดปริมาณงานที่ดีที่สุดที่ทำได้ในปัจจุบัน best_throughput การเพิ่มประสิทธิภาพ B&B ประกอบด้วยการกำจัดกิ่งทั้งหมดของต้นไม้ที่แสดงถึงพื้นที่โซลูชัน โดยการประเมินเวลาในการส่งข้อมูลในการแบ่งพาร์ติชันย่อย กระบวนการนี้ช่วยให้การเพิ่มประสิทธิภาพ B&B สามารถกำจัดกรณีจำนวนมากได้อย่างรวดเร็วเมื่อเทียบกับ