• CPU Trivia (Basic)
• Memory Addressing (Basic)

50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Designing an Instruction Set

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

The amount of practice problems in this set is smaller than usual because the topics learned this week is mainly to set up the knowledge required for the following week. Please head to the next problem set for more practice problem.

CPU Trivia (Basic)

1. How much memory can a 32-bit von Neumann machine have, assuming it has 32-bit address bus? Explain your answer.

   Show Answer

   `2^32` bytes because each address is also 32 bits long in a 32-bit von Neumann machine.

   
   

2. Can a CPU have as many registers as possible, in theory?

   Show Answer

   No. Addresses for each register involved in the instruction must be encoded within the instruction, i.e: `5` bits for 32 registers. An instruction is **32 bits** long for Beta architecture, so having too many registers will make encoding infeasible.

   
   

3. In Theory, which machine is least powerful but sufficient to compute each of the following functions? Choose for the four following possible choices ranked by its level of powerfullness:

   • Turing Machine (most powerful)
   • FSM
   • Combinational Logic (least powerful)
   • Uncomputable

   
   The functions in question are:

   • Function 1: A processor that executes Beta instruction set
   • Function 2: A device which takes as input the digits of a binary integer from left to right, and output 1 if the number entered so far is divisible by 6, and 0 otherwise.
   • Function 3: A device that takes a sequence of binary digits, one each milisecond clock period, and output 1 if the sequence so far contains more 1s than 0s.
   • Function 4: A device that takes as input an integer n between 0 and 20, and outputs the closing price of Apple Stock on the n\(^{th}\) trading day of year 2019 (to the nearest whole dollar)
   Show Answer

   Function 1: FSM
   Function 2: FSM
   Function 3: Turing Machine
   Function 4: Combinational Logic

   
   

Memory Addressing (Basic)

1. How many bits of addresses are required at minimum to address the following chunk of data, assuming that they are byte addressable?

0000 0100 0000 0011 0000 0010 0000 0001
1111 1111 0000 0000 1111 1111 0000 0000
1010 1010 0011 1100 0101 0011 0011 0000 
0000 0011 0010 1100 0101 1100 1100 0001
0000 0000 0000 0000 0000 1100 1100 0001