CS250 Homework Midterm Practice

Solutions


=====================================================

1. Implement the boolean function

Using the following truth table answer these questions:

x
 y
 z
 a
0
 0
 0
 1
0
 0
 1
 0
0
 1
 0
 1
0
 1
 1
 1
1
 0
 0
 1
1
 0
 1
 1
1
 1
 0
 1
1
 1
 1
 0

a) Write the boolean expression for a as a function of the inputs x, y, z using "Sum of Products". Do not simplify.

a = x'y'z' + x'yz' + x'yz+xy'z'+xy'z+xyz'

b) Write the boolean expression for a as a function of the inputs x, y, z using "Product of Sums". Do not Simplify.

a=(x+y+z')(x'y'z')

c) Using the sum of products you obtained in a) simplify the expression using only boolean algebra (no Karnaugh maps).

a = x'y'z' + x'yz' + x'yz+xy'z'+xy'z+xyz'
a=z'(x'y'+x'y+xy+xy')+x'yz+xy'z
a=z'(x'(y'+y)+x(y+y'))+x'yz+xy'z
a=z'(x'+x)+x'yz+xy'z
a=z'+x'yz+xy'z
a=z'+z(x'y+xy')
a=z'(1+x'y+xy)+z(x'y+xy')
a=z'+z'(x'y+xy)+z(x'y+xy')
a=z'+(z'+z)(x'y+xy')
a=z'+x'y+xy'

d) Write the Karnaugh map for b and simplify. Obtain the Minimum expression.
karnaugh
e) Draw  the schematic that implements this expression using  AND/OR/NOT/ gates
 
diag1

f) Draw  the schematic that implements this expression using only NAND gates.

a = z' + x'y + xy'
a = ((z'+x'y+xy')')'
a=(z(x'y+xy')')'
a=z NAND (x'y+xy')'
a=z NAND(((x'y+xy')')')'
a=z NAND(((x'y)'(xy')')'
a=z NAND((x' NAND y) NAND (x NAND y'))

diag2

2. Draw a Flip Flop


a) Using NAND gates

flip-flop-nand

b) Using NOR gates

flip-flop-nor.

3.  In each line write the name of the memory section where the variables are stored:

int a = 5;  // a is stored in _data____________

int b[20];  // b is stored in _bss____________

int main() {  // main is stored in   text _____________
{
    int x;    // x is stored in ____stack_________

    int *p = (int *)malloc(sizeof(int)); // p points to memory stored in _heap__________
}
 

4. Enumerate the steps needed to load a program.

  1. The loader allocates space for all the sections of the executable file (text, data, bss etc)
  2. It loads into memory the executable and shared libraries (if not loaded yet)
  3. It also writes (resolves) any values in the executable to point to the functions/variables in the shared libraries.(E.g. calls to printf in hello.c)
  4. Once memory image is ready, the loader jumps to the _start entry point that calls init() of all libraries and initializes static constructors.
  5. Then it calls main() and the program begins.
  6. _start also calls exit() when main() returns.
Slide 59 Slide 60

5. What is a "Dynamic Linker" and a "Static Linker".

6. Perform the following multiplication in binary. Also, convert to decimal the operands and the result.


               1001010 x 1101
          --------------
               1001010
         0000000
        1001010
       1001010
      ------------
       1111000010

7.  Perform the following division in binary, Also, convert to decimal the operands and the result.


                               11011             
                 1011 | 100101001
                       - 1011
                        -----
                        001111
                        - 1011
                        ------
                          010000
                         -  1011
                           -----
                           001011
                          -  1011
                           ------
                             0000


8.  Represent the number1.25 in binary using the IEEE 754 double representation. The formula is given:


Val in decimal = (-1)s x (1.m) x 2(e-bias) where:

bias = 1023
s = bit 63
e = bits 52 to 62
m= bits 0 to 51

   
1.25(base 10) = 1.01(base 2) x 20
s = 0
m = .01 (base 2)
e-bias = 0 ==> e - 1023 = 0 ==> e = 1023(base 10) = 01111111111(base 10)



Val in binary: _1 _01111111111 0100000000 0000000000 0000000000 0000000000 00_________________________


9.  Explain what is a "Pipe Stall" and how can be avoided.

A pipe stall happens when an instruction needs the result of the previous instruction in order to be able to execute. This causes the next instruction to have to wait blocking the execution pipe line.

Also a pipe stall happens when a branch instruction causes all next instructions to be thrown out from the pipeline.

Also, a pipe stall may happen when accessing main memory in RAM causes one instruction to block the pipe line.

10. Obtain the representation of number -58 using 8 bits. Verify that 78 + (-58) is equal to 20 using binary addition and complements of 2.

58 (base 10 ) = 111010 (base 2)

Convert to binary and subtract 1:
     00111010 - 1 = 00111001
Flipping bits:
     ~00111001 = 11000110

-58 (base 10) =  11000110

78 (base 10) = 01001110(base 2)
78 +(-58) = 01001110 + 11000110 = 00010100 (base 2) (eliminate bits beyond 8 bits) = 20 (base 10)

11. Write a function "int isBigEndian()" that will return 1 if the computer is big endian or 0 if it is little endian.


int isLittleEndian()
{
     int i = 5;
     char *  p = (char *) &i;
      if (*p==5) {
        return 1;
     }
     return 0;
}

12. What is the difference between Harvard Architecture and Von Newman Architecture

Von Newman Architecture stores program and data in the same memory space.

In a Hardvard Architecture program and data are stored in separate memory spaces.

13. What do CISC and RISC stand for and enumerate the characteristics of each.

CISC

RISC


14. Reorder the following instructions to prevent a pipe stall:

ADD r1, r1, r4
SUB  r2, r1,r3
ADD r5, r6, r7
SUB  r8, r5, r9
ADD r10, r11, r12
SUB  r13, r10, r4

Reordering:

ADD r1, r1, r4
         ADD r5, r6, r7
         ADD r10, r11, r12
         SUB  r2, r1,r3
         SUB  r8, r5, r9
         SUB  r13, r10, r4

15. In ARM Assembly language write a program that prints "Hello CS250"

.text
      .global main
main:
      stmfd   sp!, {fp, lr}
       ldr     r0, .L2
       bl      printf
      ldmfd   sp!, {fp, pc}
.L2:
      .word   .LC0

      .section        .rodata
.LC0:
      .ascii  "Hello cs250\n\000"

16. In ARM Assembly language implement a program "maxmin" that prompts two integer numbers fom stdin and then displays the maximum, minimum and average of both: numbers. Here is an example of the usage:


bash> maxmin
a=5
b=8
max=8
min=5
avg=6

.section        .rodata
promptA:
        .ascii  "a: \000"
promptB:
        .ascii  "b: \000"
readA:
        .ascii  "%d\000"
readB:
        .ascii  "%d\000"
printMax:
        .ascii  "max=%d\n\000"
printMin:
        .ascii  "min=%d\n\000"
printAvg:
        .ascii  "avg=%d\n\000"

.section .data
        .align 2

        /* Define variable 4 bytes each aligned to 4 bytes
           int a;
           int b;
         */
        .comm   a,4,4
        .comm   b,4,4

        .text

        /* We need to store the addresses of a and b
           in .text to be able to access them in main */

addra:  .word a
addrb:  .word b
addrPromptA: .word promptA
addrPromptB: .word promptB
addrReadA: .word readA
addrReadB: .word readB
addrPrintMax: .word printMax
addrPrintMin: .word printMin
addrPrintAvg: .word printAvg


.global main            /* main() { */
main:
        stmfd   sp!, {fp, lr}           /* Save pc and lr */

        ldr     r0, addrPromptA         /* Prompt a */
        bl      printf

        ldr     r0, addrReadA           /* Read a */
        ldr     r1, addra
        bl      scanf

        ldr     r0, addrPromptB         /* Prompt b */
        bl      printf

        ldr     r0, addrReadB           /* Read b */
        ldr     r1, addrb
        bl      scanf

        ldr     r0, addra               /* r0<- a */
        ldr     r0, [r0]
        ldr     r1, addrb             /* r1<- b */
        ldr     r1, [r1]

        cmp     r1,r0                 /* Compute max(a,b)
        bgt     bgreater              /*b is larger. skip. */
        mov     r1,r0                 /* put a in r1*/
agreater:

        ldr     r0, addrPrintMax        /* print Max */
        bl      printf

        ldr     r0, addra               /* r0<- a */
        ldr     r0, [r0]
        ldr     r1, addrb             /* r1<- b */
        ldr     r1, [r1]

        cmp     r1,r0                 /* Compute min(a,b)
        blt     bsmaller              /*b is smaller. skip. */
        mov     r0,r1                 /* put a in r1*/
asmaller:

        ldr     r0, addrPrintMin        /* print Min */
        bl      printf
        
        ldr     r0, addra               /* r0<- a */
        ldr     r0, [r0]
        ldr     r1, addrb             /* r1<- b */
        ldr     r1, [r1]
        add     r1, r1, r0            /* r1 = a + b; */
        mov     r2, #2
        sdiv    r1, r1, r2            /* r1 = (a + b)/2 */
        
        ldr     r0, addrPrintAvg        /* print Average*/
        bl      printf
  
        ldmfd   sp!, {fp, pc}   /* return from main */

                                /* } */

17. In ARM Assembly language implement the function int addarray(int n, int * array) that add all the elements of the array passed as parameter. n is the length of the array.

maxarray.s
/* Find maximum of an array of integers. Called from "C"
  extern int maxarray(int *a, int n);
*/
        .text

        .global addarray       /* maxarray(int n, int *a) { */
                                        /* n: r0 */
                                        /* a: r1 */
addarray:
        stmfd   sp!, {r4, r5, fp, lr}   
                               /* Save pc, lr, r4, r5 */

        mov     r2,#0                 /* sum: r2  */
                                        /* sum= 0 */

        mov     r3,#0                   /* i: r3 */
                                        /* i=0; */
while:
        cmp     r3,r1        /* while (i!=n) { */
        beq     endsum

        mov     r4,r3        /* r4=a[i] */
        mov     r5,#4
        mul     r4,r4,r5
        add     r4,r1,r4 /* as r4=*(int*)((char*)a+4*i)*/
        ldr     r4,[r4]

        add     r2, r2,r4      /* sum += a[i] */

	mov     r5,#1      /* i++; */
        add     r3,r3,r5

        bal     while      /* Go back to while */
endsum:

        mov     r0,r2

        ldmfd   sp!, {r4, r5, fp, pc}   
                          /* return from main */

                         /* } */


18. Write the implementation of int mystrlen(char * s)  in ARM assembly language.

/* Get length of a string. 
  extern int strlen(char *s);
*/
        .text

        .global mystrlen
                                        /* s: r0 */
                                        
mystrlen:
        stmfd   sp!, {fp, lr}       /* Save pc, lr, r4*/

                                        /* Count chars in a */
        mov r1, #0                      /* len : r1; len = 0; */

skip:
        ldrb    r2,[r0]                 /* r2 <- *a */
        mov     r3,#0
        cmp     r2,r3
        beq     endskip                 /* if (*a == 0) jump endskip */
        mov     r3,#1
        add     r0,r0,r3                /* a++ */
        add     r1, r1, r3              /* len++ */
        bal     skip                    /* go to skip */

endskip:
        mov r1, r0                      / Return len */

        ldmfd   sp!, {fp, pc}

19. Complete the function memdump(char *p, int len) in the following program that dumps in hexadecimal byte by byte the memory starting at p len bytes. An example output is given at the end of the program.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void memdump(char * p , int len) {
    int i;
    int j;
    for (i=0; i < len; i++) {
      printf("0x%08x: ",p);

      int n = len - i;
      if ( n > 16 ) n = 16;
      for (j = 0; j < n; j++) {
          printf("%02x ", *(unsigned char *) (p+j) );
      }
      for (;j<16;j++) {
        printf("   ");
      }
      for (j = 0; j < n; j++) {
          printf("%c", ((*p)>=32 && (*p) <= 127)?*p:'.');
          p ++;
          i ++;
      }
      printf("\n");
    }
}
Typical output:
0xbeab36e0: 41 76 00 40 09 00 00 00 30 00 00 00 e4 36 ab be Av.@....0....6..
0xbeab36f0: 00 00 00 00 00 00 28 40 48 65 6c 6c 6f 20 77 6f ......(@Hello wo
0xbeab3700: 72 6c 64 0a 00 88 00 00 80 2b 2f 40 c0 87 00 00 rld......+/@....
0xbeab3710: fb ff ff ff 05 00 00 00 00 00 00 00 00 00 00 00 ................