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

Using load-store:

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

2. 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:

F₀F₁ = 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:

F₀F₁ = 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. F₀F₁ = 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.

2. 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’)

3. Booth Multiplication Algorithm:

/***********************************************************

Title: Booth Algorithm sample

Desc: To simulate booth multiplication algorithm

Author: Buhadram

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)

#define BITMASK(x,mask) 	((x) & mask)

/*********************************

proc: bitmask

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) {

	   *head++ = '-';

       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';

	memcpy(head, ++tail, i);

    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;

}