विभिन्न प्रकार के SIMD मशीन इंटरकनेक्शन नेटवर्क की सार्वभौमिकता

SIMD मशीन आर्किटेक्ट्स को इंटरप्रोसेसर संचार प्रदान करने के लिए एक इंटरकनेक्शन नेटवर्क चुनना चाहिए। नेटवर्क की सार्वभौमिकता इसकी प्रोसेसिंग तत्वों के मनमर्जी इंटरकनेक्शन को अनुकरण करने की क्षमता है। हम पाँच विशेष नेटवर्क की सार्वभौमिकता की जांच करते हैं जो Illiac IV, STARAN, Omen, SIMDA, और RAP मशीनों में उपयोग किए गए प्रकारों को कवर करते हैं। ये Feng, Lang, Lawrie, Orcutt, Siegel, और Stone द्वारा चर्चा किए गए प्रकारों को भी कवर करते हैं। हम Perfect Shuffle, PM21, WPM21, और Cube नेटवर्क के लिए O((log2N)2) एल्गोरिदम देते हैं, जहाँ N प्रोसेसिंग तत्वों की संख्या है, ताकि मनमर्जी इंटरकनेक्शन का अनुकरण किया जा सके (Orcutt ने Illiac नेटवर्क के लिए O(N1/2log2N) एल्गोरिदम दिया है)। हम Batcher की बिटोनिक सॉर्टिंग विधि का विश्लेषण करते हैं और दिखाते हैं कि प्रत्येक नेटवर्क इसे SIMD मशीन पर कैसे लागू कर सकता है। हम यह चर्चा करते हैं कि सॉर्टिंग डेस्टिनेशन टैग्स इंटरकनेक्शनों के अनुकरण के समान है।