## Sunday, March 11, 2012

### Computer Design Fun Party!

1. To compute expression A = (B-C)*(D-E)

Using accumulator:

Load B ; acc = B; opcode=1 B, oper=2B; mem.traf = 2 B
Sub C ; acc = B – C; 1 byte opcode, 2-bytes operand = 3 bytes
Store A ; A = B -C; 1 byte opcode, 2-bytes operand = 3 bytes
Load D ; acc = D; 1 byte opcode, 2-bytes operand = 3 bytes
Sub E ; acc = D -E; 1 byte opcode, 2-bytes operand = 3 bytes
Mul A ; acc = (B-C)* (D-E) ; 1 byte opcode, 2-bytes operand = 3 bytes
Store A ; A = (B-C) * (D-E) ; 1 byte opcode, 2-bytes operand = 3 bytes

Assume each opcode takes 8-bit, operands are 16-bit and data is move in 16-bit chunks:
Total bytes: 7 * 3 byte = 21 bytes
Memory traffic: 21 + 7 * 2 = 35 bytes

Ld B, r1 ; r1 = B; opcode=1 B, op = 2 B; mem. traff = 2 bytes
Ld C, r2 ; r2 = C; memory traffic = 2 bytes
Sub r1, r2,r3 ; r3 = r1 * r2 = B – C; size=2 bytes, memory traffic = 0
Ld D, r1 ; r1 = D; memory traffic = 2 bytes
Ld E, r2 ; r2 = E; memory traffic = 2 bytes
Sub r1,r2,r4 ; r4 = r1 * r2 = D-E; memory traffic = 0 bytes
Mul r3, r4, r1 ; r1 = r3 * r4 = (B-C) * (D-E); memory traffic = 0 bytes
St r1,A ; A = r1 = (B-C) * (D-E); memory traffic = 2 bytes

Number of bytes for instructions: 3*7 = 21 bytes
Memory traffic: 21 + 5 *2 = 31 bytes

Using stack:

Push B ; mem. Traf = 2 bytes
Push C ; mem. Traf = 2 bytes
Sub ; B – C; mem. Traf. = 2 bytes
Push D ; mem traf = 2 bytes
Push E ; mem.traf = 2 bytes
Sub ; top of the stack contains D-E, below it is B-C
Mul ; top of the stack now contains (B-C) * (D-E)

Each instruction occupies 3 bytes (1 byte opcode and 2-byte operand), so total instructions use 3*7 = 21 bytes.
Memory traffic: 21 + 2*7 = 35 bytes

1. Register 0, 1, 2 (R0, R1, R2) are GPRs. R3 is initialized to 1 and make sure it is unchanged.
1. Control sequence that forms the 2’s complement difference (or, R0 ← R0 + (-R1) = R0 + 2’s complement of R1) of the contents of R0 and R1:

 Write Enable A-bus enables B-bus enables F0­F1 Time 0 1 2 3 0 1 2 3 0 1 2 3 F0 F1 T 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 2

Explanation:
At T=0:
F0F1 = 11 (A’), A-bus enable = 1, B-bus enable = all zeros. Data (say, Y) is placed in A-bus. C-bus contains Y’, Write-enable = pin 1. So Y is written to register 1 (R1 = Y’).
At T = 1:
F0F1 = 00 (add), A-bus enable = pin 1 (content of R1 which is X, is in A-bus), B-bus enable= pin 3 (content of R3 which is 1 is in B-bus), write-enable = pin 1 (C-bus contains Y’ + 1). So R1 = Y’ + 1 = 2’s compl. Of X.(or R1 = -Y)
At T = 2
B-bus = 0, hence data from R0, say X, is placed in B-bus. F0F1 = 00 (add), A-bus enable = 1 (which contains –Y). C-bus contains R0 + R1 = X - Y . Write-enable = pin 0, so result is stored in R0.

1. R0 XOR R1 (R0’ & R1 + R0 & R1’) = (R0 + R1)(R0’ + R1’), leaving the result in R0.

 Write Enable A-bus enables B-bus enables F0­F1 Time Note 0 1 2 3 0 1 2 3 0 1 2 3 F0 F1 T (Movements etc.) 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 R2 ← A + B 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 R0 ← A’ 0 1 0 0 0 1 0 0 0 0 0 0 1 1 2 R1 ← B’ 0 1 0 0 1 0 0 0 0 1 0 0 0 0 3 R1 ← A’ + B’ 1 0 0 0 0 1 0 0 0 0 1 0 1 4 R0 ← (A+B)&(A’+B’)

1. Booth Multiplication Algorithm:

```/***********************************************************
Title: Booth Algorithm sample
Desc: To simulate booth multiplication algorithm
Notes:

Ref:
- Computer Architecture: A Quantitative Approach
*************************************************************/
#include
#include
#include
#include

#define NUMTYPE	   	short int
#define NUMBITS		(8*sizeof(NUMTYPE))
#define MAX(x,y) 		((x) > (y) ? x : y)
#define MIN(x,y) 		((x) < (y) ? x : y)
/*********************************
desc: return 1 if bit[pos] is set
pos=0 for LSB, and p=sizeof(x)-1
for MSB
*********************************/
#define BIT(x,pos)		( (BITMASK(x,1<<(pos))) >> (pos) )
#define ASCII_BIT(x)	((x) + '0')

char *get_input(const char *prompt, char *buf, int length)
{
char *p;
int i;
printf("%s",prompt);
// fgets is safer to avoid buffer overflow
p = fgets(buf, length, stdin);
// remove newline character
buf[strlen(buf)-1] = 0;
return p;
}

/********************************************
* Swapbits
* Desc: To swap bit orders, e.g LSB becomes MSB
Note: b[0] is LSB, b[n-1] is MSB
********************************************/
void swapbits(NUMTYPE *b)
{
int i;
int tmp;

tmp = 0;
for(i=0; i base)
base = 10;                    /* can only use 0-9, A-Z        */
tail = &buf[BUFSIZE - 1];           /* last character position      */
*tail-- = '\0';

if (10 == base && N < 0L) {
uarg = -N;
}
else uarg = N;

if (uarg) {
for (i = 1; uarg; ++i) {
register ldiv_t r;
r = ldiv(uarg, base);
*tail-- = (char)(r.rem + ((9L < r.rem) ? ('A' - 10L) : '0'));
uarg    = r.quot;
}
}
else  *tail-- = '0';
return str;
}

#endif

/******************************
proc: btol
desc: converts binary string to
long integer
******************************/
long btol(const char *bin)
{
int n,i;
long d;

n = strlen(bin);
d = 0;
for(i=n-1; i>=0; i--) {
d += (bin[i]-'0') * (1 << i);
}
return d;
}

/**************************************
Proc: Ashift_bits_right
desc: perform arithmetic shift right on
bits in x, but preserving the sign bit.
***************************************/
void ashift_bits_right(long *x, int numbits)
{
int neg;

neg = (*x<0) ? 1 : 0;
*x >>= numbits;

if (neg)
//*x |= (1<>= 1;
qm = q0;
q >>= 1;
if (a0)
r |= b1;
b1 <<= 1;
}
return r;
}

int main(int argc, char *argv[])
{
#define BUF_SIZE	(1024+1)
char *buf;
NUMTYPE A, B;
long res;
char str[256];

buf = (char *)malloc(BUF_SIZE+1);
assert(buf);
get_input("A = ", buf, BUF_SIZE);
A = atol(buf);
printf("A (in Binary) = %s\n", ltoa(A, str, 2));
get_input("B = ", buf, BUF_SIZE);
B = atol(buf);
printf("B (in Binary) = %s\n", ltoa(B, str, 2));
res = A+B;
printf("A + B = %ld = 0x%0X\n", res, res);
res = A - B;
printf("A - B = %ld = 0x%0X\n", res, res);
puts("\n\nBOOTH MULTIPLICATION\n");
res = booth_mult(A,B);
printf("A * B = %ld = 0x%0X = %sb\n", res, res, ltoa(B,str,2));
free(buf);
return 0;
}
```