::. GRAPH TERMINOLOGY .::

SOME APPLICATIONS OF SPECIAL TYPES OF GRAPHS

เราสามารถแสดงกราฟแบบพิเศษที่ใช้ในmodel ของ การติดต่อสื่อสารของข้อมูล (data communication) และการประมวลผลแบบขนาน(parallel processing) ตัวอย่างที่12 Local Area Network(LAN) คอมพิวเตอร์ที่หลากหลาย เช่น มินิคอมพิวเตอร์ และ คอมพิวเตอร์ ส่วนบุคคล เช่นเดียวกับอุปกรณ์ที่ติดต่อภายนอก เช่น printer และ plotters ในการสร้างสามารถทำการติดต่อ กันโดยใช้ local area network บาง network สร้างเป็นแบบ star topology ที่ซึ่ง device ทั้งหมดจะติดต่อกับ central control device . Local Area Network สามารถแสดงได้ด้วยการใช้ complete bipartite graph K_l,n ดังที่แสดงใน Figure 10(a). ข้อความจะส่งจาก device ไปที่อีก device หนึ่งโดยผ่าน central control device. Local Area Network(LAN) อื่นๆ อาจสร้างเป็นแบบ star topology ที่ซึ่งแต่ละ deviceติดต่อกันกับอีก 2 deviceอื่นๆ Local area networks ด้วย ring topology เป็น modelที่ใช้แบบ n-cycles, C_n , ดังที่แสดงใน Figure 10(b) ข้อความจะถูกส่งจาก device ไปยัง device รอบๆ cycle จนกระทั่งข้อความไปถึงผู้รับ สุดท้ายบาง local area networks ใช้ topology ร่วมกัน(Hybrid Topology) โดยข้อความอาจจะส่ง ไปรอบๆวงแหวนหรือส่งไปยัง central device ซึ่งการใช้ในลักษณะนี้ทำให้เกิดความเชื่อถือของระบบมีมากขึ้นได้ Local area networks แบบนี้เป็นการใช้ในแบบ วงล้อ(wheels) Wn ดังที่แสดงใน Figure 10

Figure 10 Star , Ring , และ Hybrid Topologies สำหรับ Local Area Network

ตัวอย่างที่13 การติดต่อกันระหว่างระบบเครือข่าย สำหรับ การคำนวณแบบขนาน เมื่อเร็วๆนี้ คอมพิวเตอร์จะ ทำการจัดการกับโปรแกรม ในหนึ่งการทำงานที่หนึ่งเวลา มีผลทำให้ algorithm ที่เขียนเพื่อการแก้ปัญหาที่ถูก ออกแบบให้ทำ 1 ขั้นตอนที่ 1 เวลา เช่น algorithm ที่ถูกเรียกว่า serial อย่างไรก็ตาม ก็ยังมีการแก้ปัญหาโดย การใช้การคำนวณที่มากมาย เช่น การจำลองสภาพอากาศ, การจำลองทางการแพทย์ ไม่สามารถแก้ปัญหาใน การให้เหตุผล ในการใช้การดำเนินการแบบ อนุกรม ได้เช่นเดียวกับบน ซุปเปอร์คอมพิวเตอร์ ยิ่งกว่านั้น ยังมีข้อ จำกัดทางด้าน กายภาพ ในการที่ทำ การดำเนินการ พื้นฐานของคอมพิวเตอร์ ดังนั้น เป็นปัญหาเสมอๆ ในการไม่ สามารถแก้ปัญหาในการใช้ การดำเนินการแบบอนุกรม Parallel processor เป็นการใช้คอมพิวเตอร์ซึ่งมี processor หลาย ๆ ตัวมาประมวลผลร่วมกัน ซึ่งใน แต่ละตัวจะมี memory เป็นของตัวเอง ซึ่งจะช่วยแก้ปัญหาในเรื่องข้อจำกัดของ serial คอมพิวเตอร์ Parallel algorithms เป็นการแก้ปัญหาโดยการแบ่งปัญหาออกเป็นส่วนย่อย ๆ ซึ่งจะทำให้แก้ปัญหาที่เกิดขึ้นได้อย่างรวด เร็ว จะใช้ได้ใน processor หลาย ๆ ตัว ใน parallel algorithms จะมีคำสั่งที่ใช้ควบคุมการส่งปัญหาที่เกิดขึ้นโดย จะส่งไปให้กับ processor ต่าง ๆ โดยจะส่ง input และ output ไปยัง processor ที่เหมาะสม เมื่อมีการประมวลผลแบบ parallel จะมี processor 1 ตัว ที่จะสร้าง output จาก processorตัวอื่นๆ เราสามารถจะเลือกใช้ชนิดของกราฟที่เหมาะสมในการแสดงการติดต่อกันของระบบของ processor ในคอมพิว เตอร์ภายในแบบ multiple processor ชนิดของการติดต่อของระบบจะใช้ parallel algorithm ที่ขึ้นอยู่กับความ ต้องการของข้อมูลที่แลกเปลี่ยนกันระหว่าง processor เช่น ความเร็วที่ต้องการ, และฮาร์ดแวร์ที่จำเป็น วิธีที่ง่ายที่สุดและไม่แพง คือ การติดต่อกันของ processor จะรวมถึงการติดต่อ 2 ทาง ระหว่างแต่ละคู่ของprocessor ระบบแสดงได้โดยK_n กราฟที่สมบูรณ์ n เมื่อใช้ processor n ตัว อย่างไรก็ตาม มีปัญหาเกี่ยวกับชนิดของการติดต่อของระบบเพราะ ความต้องการของการติดต่อมีขนาดใหญ่ ซึ่งในความเป็น จริง จำนวนการติดต่อโดยตรงของ processor จะถูกจำกัด ดังนั้นเมื่อจำนวน processor มีเยอะ processor จะ ไม่สามารถติดต่อกันได้โดยตรงทั้งหมด ตัวอย่างเช่น มี 64 processor C (64,2) = 2016 connection และแต่ละ processor จะติดต่อกันได้โดยตรงได้แค่ 63 วิธีที่ง่ายอีกวิธีหนึ่งของ n processor คือ การใช้ linear array. แต่ละ processor ใช้ P_I, ตั้งแต่ P₁ถึง P _nซึ่งจะถูกติดต่อกับ P _{n- 1}และ P _{n
+ 1}. P ₁จะติดต่อกับ P₂และ P _nจะติดต่อกับ P _{n 1}แค่ตัวเดียว. Linear array จะใช้สำหรับ processor 6 ตัว ดังในรูป11 ข้อดีของ linear array คือ แต่ละprocessor จะมีการติดต่อกับ processor อื่น ๆ ได้ 2 ทาง ข้อเสีย คือ บางครั้งจำเป็นจะต้องใช้จำนวนการ ติดต่อขนาดใหญ่ เรียกว่า hops ใช้ สำหรับ processor ที่ใช้สำหรับ processor ที่ใช้ในการ shareข้อมูลร่วมกัน Mesh network(หรือ array 2 มิติ ) เป็นวิธีพื้นฐานที่ใช้ในการติดต่อของระบบ ในระบบจำนวน processor จะเป็นสี่เหลี่ยมที่สมบูรณ์ ที่เรียกว่า n = m ²processor n ตัว ใช้ P ( I,j ), 0 ? I ? m 1,0 ? j ? m 1 การติดต่อ 2 ทาง ของ processor ใช้ P (I,j) กับอีก 4 ตัวที่ใกล้เคียงกัน. P (I ? 1, j ) และ P ( I, j ? 1 ) ข้อจำกัดของ mesh network คือ แต่ละ processor จะมีจำนวน link ที่จำกัด

รูปที่ 11 Linear array สำหรับ processor 6 ตัว

การติดต่อสื่อสารระหว่าง processor แต่ละคู่ ต้องการ O( ? n ) = O(m) กราฟแสดง mesh network สำหรับ processor 16 ตัว แสดงในรูป 12

รูปที่ 12 Mesh Network แบบมีprocessor 16 ตัว

การติดต่อของระบบที่สำคัญที่สุด เรียกว่า hypercube เช่น ในระบบ, จำนวน processor ที่ใช้มีกำลัง 2 , n = 2 ^m processor ใช้ตั้งแต่ P ₀, P ₁, P _{n 1}. แต่ละ processor มีการติดต่อ 2 ทาง กับ m processor . Processor P _Iติดต่อกับ processor ที่รวมถึง binary ที่แตกต่างกันใน 1 bit. Hypercube network ที่สมดุลจะต้องมีการติดต่อกันโดยตรงของแต่ละ processor และจำนวนการติดต่อต้องขึ้นกับ processor ที่สามารถติดต่อได้. คอมพิวเตอร์ที่สร้าง hypercube network และ parallel algorithm ต้องมีการใช้ hypercube network. กราฟ Q _nn-cube แสดง hypercube network ใน n processor . รูป 13 แสดง hypercube network สำหรับ processor 8 ตัว ( รูป 13 แสดงวิธีวาดที่แตกต่างกันของ Q ₃มากกว่าในรูปที่ 6 )

รูปที่ 13 Hypercube Network สำหรับ processor 8 ตัว