System and method for systolic array sorting of information segments

In a broadband earliest deadline first (EDF) queue, a method for sorting information segments by field rank, the method comprising:

• systolically moving information segments with lower field ranks to temporary registers higher in a sequenced order of temporary registers;
• systolically moving information segments with higher field ranks to permanent registers lower in a sequenced order of permanent registers;
• and
• pairing each temporary register with a corresponding permanent register having the same order in a sequence of neighboring registers, forming stages in a sequenced order of stages.

In an earliest deadline first (EDF) queue, a method for sorting information segments, the method comprising:

• comparing the field rankings of information segments in neighboring registers;
• in response to comparing, systolically moving information segments with lower field rankings to temporary registers higher in sequence;
• and
• in response to comparing, systolically moving information segments with higher rankings to permanent registers lower in sequence.

In an earliest deadline first queue integrated circuit, a system for sorting information segments by field rank, the system comprising:

• a sequence of stages for storing information segments having a field of sequential ranks;
• wherein each stage has a port for accepting information segment insertions from a lower sequence stage, a port for supplying extracted information segments to a lower sequence stage, a port for accepting information segment extractions from a higher sequence stage, and a port for supplying information segment insertions into a higher sequence stage;
• and
• wherein each stage accepts information segments inserted at a maximum insertion rate, and supplies information segments extracted in response to the field rank of the information segment, at a maximum extraction rate, where the maximum insertion rate is equal to twice the maximum extraction rate.

In a earliest deadline first queue integrated circuit, a system for sorting information segments by field rank, the system comprising:

• a sequence of stages for storing information segments having a field of sequential ranks;
• wherein each stage includes a temporary register having an input and an output, a permanent register having an input and an output, a port for accepting information segment insertions from a lower sequence stage, ports for supplying extracted information segments to a lower sequence stage, a port for accepting information segment extractions from a higher sequence stage, and a port for supplying information segment insertions into a higher sequence stage;
• wherein each stage accepts information segments inserted into the temporary register from a lower sequence stage at a maximum insertion rate, and accepts information segments into the permanent register extracted from a higher sequence stage, in response to the field rank of the information segment, at a maximum extraction rate equal to one-half the maximum insertion rate;
• wherein each stage includes a first comparator having a first input connected to the temporary register output, a second input connected to the output of the permanent register, and an output to supply the results of a comparison of information segment field ranks;
• wherein each stage includes a second comparator having a first input connected to the temporary register output, a second input connected to the output of a permanent register in a higher sequence stage, and an output to supply the results of a comparison of information segment field ranks;
• wherein each stage includes a third comparator having a first input connected to the temporary register output, a second input connected to the output of a temporary register in a higher sequence stage, and an output to supply the results of a comparison of information segment field ranks;
• wherein each stage includes a first multiplexor (MUX) having a first input connected to the output of the permanent register in the higher sequence stage, a second input connected to the temporary register in the higher sequence stage, a third input connected to the output of the temporary register in the same stage, a fourth input connected to the output of the permanent register in the same stage, an output connected to the input of the permanent register in the same stage, and a control input to accept MUX selection commands;
• wherein each stage includes a second MUX having a first input connected to the output of the permanent register in the same stage, a second input connected to the output of the temporary register in the same stage, an output connected to the input of the higher sequence stage temporary register input, and a control input to accept MUX selection commands;
• and
• wherein each stage includes a controller having a first input connected to the output of the first comparator, a second input connected to the output of the second comparator, a third input connected to the output of the third comparator, a fourth input to connected to the output of a second comparator in a lower sequence stage, a fifth input connected to the output of a third comparator in a lower sequence stage, a sixth input connected to the output of a first comparator in a higher sequence stage, a seventh input to accept insertion and extraction commands from a controller in a lower sequence stage, a first output connected to the control input of the first MUX, a second output connected to the control input of the second MUX, and a third output connected to the seventh input of a controller in a higher sequence stage.