Sorting using interconnection networks, Computer Networking

Assignment Help:

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


Related Discussions:- Sorting using interconnection networks

Disadvantage of vpns - point to point , Disadvantage of VPNs The disad...

Disadvantage of VPNs The disadvantages of VPN  are related to implementation troubleshooting  trust and  internet  availability. a.Implementation  can be time consuming: Im

What do you understand by the term lan, Question: (a) What do you mean...

Question: (a) What do you meant by the term ‘LAN'? How is a LAN different from a WAN? (b) Explain three types of cables which are commonly used with LANs. (c) Three com

Explain about bridges, Bridges The bridge function is to attach separat...

Bridges The bridge function is to attach separate homogeneous networks. Bridges map the Ethernet address of the nodes residing on each network segment and allow only essential

Show the flow characteristics, Q. Show the Flow characteristics? Flow ...

Q. Show the Flow characteristics? Flow characteristics Reliability - if lacking means that packets or ACKs are lost - more important with FTP, SMTP than with audio

Ospf - open shortest path first , OSPF ( open Shortest Path First) Open...

OSPF ( open Shortest Path First) Open shortest  path first  is a routing  protocols  developed for internet protocols networks by the  interior  gateway protocols working group

Low-earth-orbiting leo satellites , LOW-Earth Orbiting have more advantageo...

LOW-Earth Orbiting have more advantageous in Mobile based communication devices like PDAs, Cell phones and automobile communications. The LOW-Earth Orbiting is a satellite of orbit

Fiber optic extension, FIBER OPTIC EXTENSION:  The LAN extension using f...

FIBER OPTIC EXTENSION:  The LAN extension using fiber optic is given in the figure below:   Figure The fiber-modem translates digital data into pulses of light the

Describe about data communications, Q. Describe about Data Communications? ...

Q. Describe about Data Communications? - Data - Information presented in whatsoever form is agreed upon by the parties creating and using the data - Data Communications - ex

Name the layers of osi, List the layers of OSI There are seven layers i...

List the layers of OSI There are seven layers in OSI model a. Physical Layer b. Data Link Layer c. Network Layer d. Transport Layer e. Session Layer f. Presen

What are some drawbacks of implementing a ring topology, What are some draw...

What are some drawbacks of implementing a ring topology? In case one workstation on the network varies a malfunction, it can bring down the whole network. Another drawback is t

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd