Problem

Give integers n and k, list all numbers from 1 n in directory order, then return $k^{th}$ number in that list.

Logic

Intuitively, we can generate all numbers $[1..n]$, convert to string, sort, resulting to an $O(O log n)$.
Brutely, we can have the following code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int findKthNumber(int n, int k) {
        vector<string> nums;
        
        for (int i = 1; i <= n; i++) {
            nums.push_back(to_string(i));
        }
        
        sort(nums.begin(), nums.end());

        return stoi(nums[k - 1]);
    }
};

No surprise, Time Limit Exceeded.

The directory sequence corresponds to a 10-ary prefix tree of numbers. Each node x has children x0, x1,...,x9(of course if it still <=n ).

We can count how many nodes are in each subtree and skip entire subtree when their size < k.
we can have following solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;// 0-indexed

        while(k > 0){
                int steps = countSteps(n, curr, curr + 1);
                if(steps <= k){
                //skip this subtree, go to next sibling
                        curr++;
                        k -= steps;
                }
                else{
                //answer is in this subtree let's go deeper
                        curr *= 10;
                        k--;
                }
        }
        return curr;
    }
};

countStep will calculate how many numbers exist with a prefix between ‘curr’ and ‘next’, and it should be <=n.

1
2
3
4
5
6
7
8
9

static long countSteps(long long curr, long long next, long n){
      int steps = 0;
        while (curr <= n) {
            steps += min((long long)n + 1, next) - curr;
            curr *= 10;
            next *= 10;
        }
        return steps;
}

In this lab we are required to build a hardware model for accumulation of a sequence of Bfloat16 values and implement it on the lab board.Here we assume all values are positive and no overflow will occur. Each input
Value is set by the switches and the accumulative result for each new input is displayed on the LED array.

Since we have a bottom to make operation compute, we may need a FSM. Intuitively, we will only need 2 state “idle & compute”.

Common Performance Metrics

• Latency: response time, execution time, elapsed time

• Throughout: amount work per unit time

Objected oriented programming(OOP)

In procedural programming languages(like C), programming like to be action-oriented, whereas in JAVA - programming is Object-oriented.

In OOP, programmer like to defined their own self-defined types, called classes.

Each class will contain the data and the set of the method that manipulate the data.

A user defined type(eg.class) is called a object.

Inheritance

Inheritance relations form tree-like hierarchical structure.
(eg. postgraduate students is a subclass of students)

In a “Is a” relationship, an object of a subclass may also be treated as an object
of superclass.

In a “Has a” relationship, a class object has an object of another class to store its
state or do its work. It “has-a” reference to that other object.

Designing a Class

1. Always try to keep data private
2. Creating an object may require different actions such as initialization
3. Break up class with many responsibilities

Super classes, Object, and Class Hierarchy

• Every class have a superclass
• If we don’t define the superclass, by default, it will be the class Object

Object class

• It is the only class that does not have a superclass

Often we need to override the following methods

• toString()
• equals()
• hasCode()

Abstract classes

Using Abstract classes, we can declare classes that define ONLY part of implementation, leaving extended classes to provide specific implementation of some or all the methods

One good example will be

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public abstract class Shape {

	public abstract double area();

	public abstract double circumference();

	protected static int count_shapes = 0;

	public void printArea() {
		System.out.println(" (from Shape abstract class, method printArea)> area is: " + this.area());
	}

}

public class Rectangle extends Shape {
	protected double width, height;

	public Rectangle() {
		width = 1.0;
		height = 1.0;
		count_shapes++;
	}

	public Rectangle(double w, double h) {
		this.width = w;
		this.height = h;
		count_shapes++;
	}

	public double area() {
		return width * height;
	}

	public double circumference() {
		return 2 * (width + height);
	}

}

We can also invokeshapes[].area(). Java will automatically use the implementation.

Interfaces in JAVA

All the methods defined within an interface are implicitly abstract.

Mips interpretion

Here is a traditional loop in C

1
2

while(save[i] == K)
  i+= 1;

Assume that i and k correspond to registers $s3 and $s5 and the base of the array save is in $s6. What is the MIPS assembly code corresponding to this C segment?

1
2
3
4
5
6
7

Loop: sll  $t1 $s3 2 
      add  $t1 $t1 $s6
      lw   $t0,0($t1)
      bne  $t0,$s5, Exit
      addi $s3,$s3, 1
      j    loop
Exit:

Signed Versus Unsigned Comparison

Suppose register $s0 has the binary number
$$ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111_{two}$$
and that register $s1 has the binary number
$$ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0001_{two}$$
where are the values pf registers $t0 and $t1 after these two instructions?

1
2

slt      $t0, $s0, $s1
sltu     $t1, $s0, $s1

The key spot of the question is $s0 represents $-1_{ten}$ if it is a signed integer and $2^{32} - 1_{ten}$ if it is an unsigned integer. And the value in $s1 represents $1_{ten}$ in either case.

Jump opreation in MIPS

The jump register instruction jumps to the address stored in register $ra which is just what we want. Thus, the calling program, or caller, puts the parameter values in $a0–$a3 and uses jal X to jump to procedure X (sometimes named the callee). The callee then performs the calculations, places the results in $v0 and $v1, and returns control to the caller using jr $ra.

Using more registers

We may have such question, What if we have a procedure which require more than 4 arguments and 2 return value registers. This situation is an example in which we need to spill registers to memory.

Here we need to use a data structure called stack. A stack needs a pointer to the most recently allocated address in the stack to show where the next procedure should place the registers to be spilled or where old register values are found.By historical precedent, stacks “grow” from higher addresses to lower addresses.

Compiling a C Procedure That Doesn’t Call Another Procedure:

1
2
3
4
5
6

int leaf_example(int g, int h, int i, int j) 
{  
  int f;  
  f = (g + h) – (i + j); 
  return f; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

addi $sp, $sp, –12 
sw $t1,8($sp) 
sw $t0,4($sp)  
sw $s0,0($sp) 

add $t0,$a0,$a1 
add $t1,$a2,$a3
sub $s0,$t0,$t1 

add $v0,$s0,$zero

lw $s0, 0($sp)
lw $t0, 4($sp) 
lw $t1, 8($sp)
addi $sp,$sp,12
jr $ra

Decoding machine code

What is the assembly language statement corresponding to this machine instruction?
00af8020hex

The first step in converting hexadecimal to binary is to find the op fields:

1
2

0    0    a    f    8    0    2    0  
0000 0000 1010 1111 0100 0000 0010 0000

op field is 000000 in op(31:26) rs is 00101 rt is 01111 rd is 10000 shamt is 00000 funct is 100000

By look up table we can know it is
add $s0, $a1, $t7

I. What is the range of addresses for conditional branches in MIPS (K = 1024)?

1. Addresses between 0 and 64K # 1
2. Addresses between 0 and 256K # 1
3. Addresses up to about 32K before the branch to about 32K after
4. Addresses up to about 128K before the branch to about 128K after

Conditional branches use I-type format
16-bit immediate field for the branch offset
The offset is signed
The offset represents the number of words to branch not bytes
Hence it will be $2^{16}$ words, $2^{15}$ words, $2^{17}$ bytes ahead and backward.
which is 128KB ahead and backward.

typical steps of processor design

For datapath

1. Analyse instruction set to determine the datapath requirements

2. Select a set of hardware components for the datapath and establish clocking methodology

3. Assemble datapath to meet the requirements

For control

4. Analyse implementation of each instruction to determine control points/signals on the datapath

5. Assemble the control logic

step 1

For each instruction, its requirement can be identified as a set of transfer operation.

Register lever language(RTL) is used to describe the instruction execution.eg.

1

$3 <-- $2 + $1 is for ADDU $3 $2 $1

Datapath mush support each transfer operation.

All instruction start by fetching instruction.

THen followed by different operation
All instruction should be followed with a

1

PC <- PC + 4

eg

1
2

BEQ 
If (R[rs] == R[rt]) then PC <- PC +4 + sign_ext(Imm16) || 00 else  PC <- PC + 4

step 2

For combinational logical elements, we need adder, MUX, ALU obviously and

For storage we need some registers (which is 32-bit input and output, and Write enable input) and memory(which is have 32 bit data in and 32 bit date out)

For simple and robust, we use Edge triggered clocking, all storage elements are usually clocked by the same clock edge.

We have 3 time issues need to be considered. Clock skew, setup time, hold time.

2 requirement
$\text{cycle time} >= \text{clk to Q} + \text{longest delay path} + \text{setup} + |\text{clk skew}|$
$\text{clk to Q} + \text{shortest delay path} - \text{clock skew} > |\text{hold time}|$

step 3

Put the selected components together

step 4

instruction encoding defines how instruction and their argument are represented as binary values - machine instructions.