Sorting using interconnection networks, Computer Networking

The combinational circuits use the comparators for comparing the storing and number them on the basis of minimum and maximum functions. Likewise, in the interconnection networks the two processors perform the computation of minimum and maximum functions in the following way:

Let us consider there are two processors pj and pi. Each of these processors has been given as input a part of the sequence, say ej and ei. Now, the processor pi sends the element ei to pj and processor pj sends ej to pi. After that, processor pi determine the minimum of ei and ej i.e., min (ei,ej) and processor pj determine the maximum of ei and ej, i.e. max (ei,ej). The above method is called as compare-exchange and it has been depicted in the Figure .

581_Illustration of Exchange-cum-Comparison in interconnection networks.png

                                                          Illustration of Exchange-cum-Comparison in interconnection networks

 The sorting problem chosen is bubble sort and the interconnection network can be depicted as n processors interconnected with each other in the type of a linear array as given in Figure. The method adopted for solving the bubble sort is called as odd- even transposition. Suppose an input series is B=(b1, b2, b3, b4......... bn) and each number is assigned to a particular processor. In the odd-even transposition,the sorting is executed with the help of two phases known as odd phase and even phase. In the odd phase, the elements stored in (p1, p2), (p3, p4), (p5, p6)......... (pn-1, pn) are compared according to the Figure and consequently exchanged if required i.e. if they are out of sort. In the even phase, the elements stored in (p2, p3), (p4, p5), (p6, p7)......... (pn-2, pn-1) are compared according to the Figure and consequently exchanged if required, i.e. if they are out of order. keep in mind, in the even phase the elements stored in p1 and pn are not exchanged and compared. The total number of phases needed for sorting the numbers is n i.e. n/2 odd phases and n/2 even phases. The algorithmic representation of the above discussed odd- even transposition is given below:

2084_Interconnection network in the form of a Linear Array.png

                                                Interconnection network in the form of a Linear Array

Posted Date: 3/2/2013 6:51:01 AM | Location : United States







Related Discussions:- Sorting using interconnection networks, Assignment Help, Ask Question on Sorting using interconnection networks, Get Answer, Expert's Help, Sorting using interconnection networks Discussions

Write discussion on Sorting using interconnection networks
Your posts are moderated
Related Questions
a) An Introduction/Overview of Network Security issues. b) A Risk Assessment  analysis- to include:             Assets                                                         T

ACK Received If an ACK is received by the  sender. The  SR sender marks  that packet  as having  been received by the receiver.

Path  Overhead It is part  of SPE  and contain followings  information: Performance monitor of synchronous transport , signal , path , track ,parity ,checks,  and path  status.

Which protocol comes under Hybrid dynamic type? Ans)  EIGRP (ENHANCED INTERIOR GATEWAY ROUTING PROTOCOL) comes under hybrid dynamic.

Receive Window This  field  defines the size  of the  window in bytes  that the  other party  must  maintain. Note  that the  length  of this  field 16 bits  which  means

The Five steps to data encapsulation (IN ORDER): 1) User information is changed into data. 2) Data is changed into segments. 3) Segments are changed into datagram and pack

Question: (a) How can governments provide the mobile industry with the long-term clarity and certainty it needs to make substantial capital investments in new networks? (b)

Q. Error Detection-General? Sender transmits every data unit twice Receiver performs bit-by-bit comparison between those two versions of data. Any mismatch would

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

In the following section, we shall discuss the algorithms for solving the matrix multiplication difficulty using the parallel models. Matrix Multiplication Problem Let ther