Introduction:-

With inany important applications in switching networks image processing , and data processing , parallel sorting networks have received a lot of attentions from researchers. Recently, the research theme for parallel sorting networks [4, 51 trends to how to extend the number of sorting elements. However. if the number of sorting items increases, the Complexity of parallel sorting networks will increase largely at the same time. As far as VLSI implementation is concerned, the cost of fabrication will raise as the number of sorting items increases. In order to avoid high complexity of parallel sorting networks, Olariu proposed a methodology using a fixed size 110 sorting network and a set of memory module to extend the number of sorting elements. Basically Olariu’s idea is promising in reducing the hardware cost, but the adjustment of data flow of addressing controller in Olariu’s approach is irregular. That is to say, once we need to design some larger size sorting networks, these networks will become too difficult to extend in Olariu’s approach. In this paper, based on Olariu’s idea, using a fixed size 110 sorting network and a set of memory module, we propose a modular and regular addressing method to design larger size sorting networks. In this method, the time complexity of comparing and exchanging data is O(MogN). To verify this approach, we use Verilog VHDL to design a 128-item merge-sorting network in this paper. Experimental results show that the proposed 128-item merge-sorting network can reduce both the complexity of parallel sorting networks and the cost of fabrication. Moreover, no extra data memory space is needed in this method.

Abstract:-

A hardware design approach for merge-sorting network

In this paper, a hardware design methodology for merge-sorting networks, which uses a fixed size Batcher’s sorting network, a data memory module and a memory addressing controller, is proposed. In this method, only by adjusting the data flow of the memory addressing controller, the amount of sorting data can be extended easily. Particularly, the adjustment of data flow is quite regular. Therefore, the proposed method has the following merits: low complexity of parallel sorting networks, low hardware fabrication cost, high extensibility, high regularity and no extra data memory space needed. For verifying the proposed approach, a 128-item inerge-sorting network has been designed and simulated by Verilog VHDL.

Verilog Code for Merge Sort:-

`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company:  VHDL Language
// Engineer:  Manohar Mohanta
// 
// Create Date:    12:29:42 01/24/2018 
// Design Name:  A hardware design approach for merge-sorting network
// Module Name:    merge_top 
// Project Name: A hardware design approach for merge-sorting network
// Target Devices: 
// Tool versions: 
// Description: 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//////////////////////////////////////////////////////////////////////////////////
module merge_top(
    input [15:0] in1,in2,in3,in4,in5,
  input rst,
  input clk,
    output [15:0] out1,out2,out3,out4,out5
    );
wire [1:0]mod;

mod3_counter mod3 (clk,rst,mod);
merge_sort sort(in1,in2,in3,in4,in5,out1,out2,out3,out4,out5,mod,clk);

endmodule