Timing circuits are a crucial compo

Timing circuits are a crucial component of VLSI chips. Here’s a simple model of such
a timing circuit. Consider a complete balanced binary tree with n leaves, where n is a
power of two. Each edge e of the tree has am associated length le, which is a positive
number. The distance from the root to a given leaf is the sum of the lengths of all the
edges on the path from the root to the leaf.
The root generates a clock signal which is propagated along the edges to the leaves.
We’ll assume that the time it takes for the signal to reach a given leaf is proportional
to the distance from the root to the leaf.
Now, if all leaves do not have the same distance from the root, then the signal will not
reach the leaves at the same time, and this is a big problem. We want the leaves to be
completely syncronized, and all to receive the signal at the same time. To make this
happen, we will have to increase the lengths of certain edges, so that all roor-to-leaf
path have the same lenght (we’re not able to shrink edge lengths). If we achieve this,
then the tree (with its new edge lengths) will be said to have zero skew. Our goal is
to achieve zero skew in a way that keeps the sum of all the edge lengths as small as
possible.
Give an algorithm that increases the lengths of certain edges so that the resulting tree
has zero skew and the total edge length is as small as possible.

ผลลัพธ์ (ไทย) 1:

ส่วนประกอบสำคัญของชิป VLSI วงจรกำหนดเวลาได้ นี่คือรูปแบบง่าย ๆ เช่นวงจรเวลา พิจารณานารีกับใบ n โดยที่ n คือความสมดุลสมบูรณ์แบบอำนาจของทั้งสอง อีขอบแต่ละต้นมีน.ความยาวสัมพันธ์เลอ ที่เป็นบวกหมายเลข ระยะทางจากรากไปใบไม้ให้เป็นผลบวกของความยาวทั้งหมดขอบบนเส้นทางจากรากไปยังใบหลักการสร้างสัญญาณนาฬิกาที่เผยแพร่ตามขอบกับใบไม้เราจะคิดว่าเวลาสัญญาณไปถึงใบไม้กำหนดสัดส่วนการห่างจากรากสู่ใบตอนนี้ ถ้าใบไม้ทั้งหมดมีราก ระยะเดียวกันจาก นั้นสัญญาณจะไม่ถึงใบไม้ในเวลาเดียวกัน และนี่คือปัญหาใหญ่ เราต้องออกให้syncronized อย่างสมบูรณ์ และทั้งหมดจะได้รับสัญญาณในเวลาเดียวกัน ต้องการนี้เกิดขึ้น เราจะต้องเพิ่มความยาวของขอบบาง เพื่อให้ทุก roor การใบเส้นทางมีความยาว (เราไม่สามารถลดขนาดความยาวขอบ) ถ้าเราบรรลุนี้แล้วต้น (มีความยาวขอบใหม่) จะกล่าวว่า มีการเอียงศูนย์ เป้าหมายของเราคือเพื่อให้เป็นศูนย์การเอียงในลักษณะที่ทำให้ผลรวมของความยาวขอบขนาดเป็นไปได้ให้เป็นอัลกอริทึมที่เพิ่มความยาวของขอบบางเพื่อที่จะได้แผนภูมิมีศูนย์การเอียง และความยาวรวมขอบเล็กที่สุด

ผลลัพธ์ (ไทย) 2:

วงจร Timing เป็นส่วนประกอบที่สำคัญของชิป VLSI นี่คือรูปแบบที่เรียบง่ายเช่น
วงจรเวลา พิจารณาที่สมบูรณ์สมดุลต้นไม้ไบนารีที่มีใบ n โดยที่ n เป็น
อำนาจของทั้งสอง แต่ละอีขอบของต้นไม้มีนที่เกี่ยวข้องมีความยาว le ซึ่งเป็นบวก
จำนวน ระยะทางจากรากใบให้เป็นผลรวมของความยาวของทุก
ขอบบนเส้นทางจากรากใบ.
รากสร้างสัญญาณนาฬิกาซึ่งจะแพร่กระจายตามขอบใบ.
เราจะคิดว่า เวลาที่ใช้ในการส่งสัญญาณไปถึงใบให้เป็นสัดส่วน
กับระยะทางจากรากใบ.
ตอนนี้ถ้าทุกใบไม่ได้มีระยะห่างจากรากแล้วสัญญาณจะไม่
ถึงใบในเวลาเดียวกัน เวลาและนี่คือปัญหาใหญ่ เราต้องการใบที่จะ
syncronized สมบูรณ์และทุกคนที่จะได้รับสัญญาณในเวลาเดียวกัน จะทำให้เรื่องนี้
เกิดขึ้นเราจะต้องมีการเพิ่มความยาวของขอบบางอย่างเพื่อให้ทุก roor ต่อใบ
เส้นทางมีความยาวเดียวกัน (ซึ่งเราไม่สามารถที่จะหดตัวความยาวขอบ) ถ้าเราบรรลุเป้าหมายนี้
แล้วต้นไม้ (ที่มีความยาวขอบใหม่) จะกล่าวว่ามีศูนย์เอียง เป้าหมายของเราคือ
เพื่อให้บรรลุศูนย์เอียงไปในทางที่ทำให้ผลรวมของทุกความยาวขอบขนาดเล็กเป็น
ไปได้.
ให้ขั้นตอนวิธีการที่ช่วยเพิ่มความยาวของขอบบางอย่างเพื่อให้ต้นไม้ที่เกิด
มีศูนย์เอียงและความยาวของขอบทั้งหมดมีขนาดเล็กเป็น ที่เป็นไปได้

ผลลัพธ์ (ไทย) 3:

วงจรเวลาเป็นองค์ประกอบสำคัญของด้วยชิป ที่นี่เป็นแบบง่ายๆเช่น
จังหวะวงจร พิจารณาสมดุลไบนารีต้นไม้สมบูรณ์ด้วยใบโดยที่ n คือ
พลังของทั้งสอง ขอบ E ของต้นไม้มีกำลังที่เกี่ยวข้องความยาวเลอซึ่งเป็นเลขบวก

ระยะทางจากรากเพื่อที่จะได้รับใบคือผลรวมของความยาวของขอบทั้งหมด
บนเส้นทางจากรากสู่ใบ
รากสร้างสัญญาณนาฬิกา ซึ่งเป็นไปตามขอบใบ
เราจะสมมติว่า เวลาที่ใช้ในการส่งสัญญาณไปให้ใบเป็นสัดส่วน
ระยะห่างจากรากสู่ใบ
ตอนนี้ถ้าทุกใบไม่มีระยะทางเดียวกันจากรากแล้ว สัญญาณจะไม่
ถึงใบในเวลาเดียวกัน และปัญหานี้เป็นปัญหาใหญ่ เราต้องการใบเป็น
syncronized อย่างสมบูรณ์ และรับสัญญาณได้ในเวลาเดียวกัน เพื่อให้นี้
เกิดขึ้น เราจะต้องเพิ่มความยาวของขอบบาง ดังนั้นทุกคน roor ทางใบ
มี ยาวเหมือนกัน ( เราไม่สามารถหดความยาวขอบ ) ถ้าเราบรรลุนี้
จากนั้นต้น ( ที่มีความยาวขอบใหม่ ) จะกล่าวว่ามีศูนย์เอียง . เป้าหมายของเราคือ
เพื่อให้บรรลุศูนย์เอียงไปในทางที่ทำให้ผลรวมของทั้งหมดขอบความยาวขนาดเล็กเป็น

ให้อัลกอริทึมที่เป็นไปได้ เพิ่มความยาวของบางขอบเพื่อให้ส่งผลให้ต้นไม้
มีศูนย์เอียงและความยาวของขอบทั้งหมดมีขนาดเล็กที่สุด .