Computer System Design Homework
1. Consider a sorting circuit that accepts 8 numbers serially and outputs the sorted sequence serially. The sorting algorithm is the classic bubble sort algorithm. The port interface is as shown in the figure below. The data is presented serially with one data item for every pulse on Input valid signal. The sorted sequence should also be output, one data item for one pulse on Output_valid signal. You can assume that you have a register file for the data storage. You would have to map an array in the algorithm to the register file in the datapath. Input_valid Output,Valid Bubble Sort Data_in Data out Figure 1: Port interface of the bubble sort circuit a) (10 pts) Write an algorithm that accepts the input sequence, sorts the sequence, and then outputs the sorted sequence. (10 pts) Based on the algorithm, derive an FSMD. (10 pts) Using the FSMD, derive a data path and identify all control signals. (10 pts) Show the port interface, next state and output functions of the controller. For the next state and output functions, symbolic states is accepted i.e., you need not perform state encoding. (5 pts) Extra credit: If you optimize your FSMD for question (b) (5 pts) Extra credit: If you optimize your Datapath for question (c) b) c) d) e) f) Clearly justify the need for these NOTE: You are free to add any input and/or output signals. additional signals. 1. Consider a sorting circuit that accepts 8 numbers serially and outputs the sorted sequence serially. The sorting algorithm is the classic bubble sort algorithm. The port interface is as shown in the figure below. The data is presented serially with one data item for every pulse on Input valid signal. The sorted sequence should also be output, one data item for one pulse on Output_valid signal. You can assume that you have a register file for the data storage. You would have to map an array in the algorithm to the register file in the datapath. Input_valid Output,Valid Bubble Sort Data_in Data out Figure 1: Port interface of the bubble sort circuit a) (10 pts) Write an algorithm that accepts the input sequence, sorts the sequence, and then outputs the sorted sequence. (10 pts) Based on the algorithm, derive an FSMD. (10 pts) Using the FSMD, derive a data path and identify all control signals. (10 pts) Show the port interface, next state and output functions of the controller. For the next state and output functions, symbolic states is accepted i.e., you need not perform state encoding. (5 pts) Extra credit: If you optimize your FSMD for question (b) (5 pts) Extra credit: If you optimize your Datapath for question (c) b) c) d) e) f) Clearly justify the need for these NOTE: You are free to add any input and/or output signals. additional signals
