09Implementation

Sort three values with child modules

Problem

Intended behavior. Sort3 returns its three inputs in ascending order on min, mid, and max. It is built only from Sort2 children, each of which compares two values and outputs them as lo and hi.

Current behavior. Two instances already exist. first orders in(0) and in(1); second orders the larger of those against in(2), so second.io.hi is the true maximum. The two smaller values that remain are routed to min and mid without ever being compared, so some input orders come out unsorted.

Task. At the TODO, instantiate one more Sort2, drive both of its inputs, and take min and mid from it. Leave Sort2 and the max connection unchanged, and keep the sorting inside child modules rather than replacing it with inline Mux logic.

Read the starter

Trace the input 2, 3, 1 through first and second, writing each lo and hi. After second, list which two values have not yet been placed and which outputs carry them.

Predict before running

The public run prints four input triples. Predict which rows the starter sorts correctly by luck and which it does not, and how many Sort2 instances the finished circuit will contain.

Run and explain

The starter prints 1,2,3 for 3,1,2 and 7,100,200 for 200,7,100, but 2,1,3 for 2,3,1 and 9,4,9 for 9,9,4. In both failing rows the smallest value entered through in(2) and reached second.io.lo, while first.io.lo was larger. After the fix every row is ascending, and the circuit contains three Sort2 instances: one per Module(new Sort2) that executes.

Completion check

Every order of three 8-bit values, including ties and the extremes 0 and 255, comes out ascending.
max is still taken from second, and every input port of every child is driven.
The design keeps Sort2 as the only comparison element.

Progressive hints

Hint 1

After second, the maximum is settled. The two remaining candidates come from two different children, and nothing has compared them yet.

Hint 2

A child's inputs are sinks in the parent, exactly like your own outputs. The new instance needs one candidate on each input, and its two outputs already have the names you need for min and mid.

Concept

A hierarchy is wiring between instances. Each Module(...) call places one more copy of a child, and the parent decides what that copy sees by driving its inputs. In this three-input network, the two remaining candidates must be compared before they can be assigned to min and mid.

Transfer experiment

Sketch a four-input sorting network built from Sort2 instances. Identify the values each comparator receives and count the instances in your design, the same way the modules chapter counts ELABORATE lines.