Computer Architecture

1.1 Number Base

Commonly Used Number Bases:

1. Decimal (base 10)

   • Symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

   • Notation:

   • Understandable by humans.

2. Binary (base 2)

   • Symbols: 0, 1

   • Notation:

   • Converting numbers to base 2 lets us represent numbers as bits!

3. Hexadecimal (base 16)

   • Symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

   • Notation:

   • A convenient shorthand for writing long sequences of bits.

Group of bits:

• 1 byte = 8 bits    2 hex digits  different values

• 1 nibble = 4 bits 1 hex digit    different values

Conversions from ten to other bases: Leftover algorithm

Convert to base-4

• Check the powers of the base. For base-4: 256, 64, 16, 4, 1.

• How many multiples of 64 fit in my number (73)?

  left over.

• How many multiples of 16 fit in my remaining number (9)?

  Still left over.

• How many multiples of 4 fit in my remaining number (9)?

  left over.

• How many multiples of 1 fit in my remaining number (1)?

  left over, which means we're done!

For example,

1.2 Unsigned Integers

• Can represent different numbers, simply convert decimal to binary!

• Smallest number: represents .

• Largest number: represents .

Overflow for Unisgned Integers:

• Overflow: Exceed the largest value and wrap back around to 0, e.g., .

• Negative overflow: Try to go below 0 and wrap around to large values, e.g., .

Conclusion:

1.3 Signed Integers

Idea: Use the left-most bit to indicate if the number is positive (0) or negative (1). This is called sign-magnitude representation.

• Smallest number: represents .

• Largest number: represents .

1.4 One's Complement

Idea: If the number is negative, flip the bits.

• is .

• is .

• Left-most bit acts like a sign bit. If it's 1, someone flipped the bits, so number must be negative.

• Smallest number: represents .

• Largest number: represents .

1.5 Two's Complement

Idea: If the number is negative, flip the bits, and add one (because we shifted to avoid double-zero).

• Smallest number: represents .

• Largest number: represents .

To convert two's complement to a signed decimal number:

• If left-most digit is 0: Read it as unsigned

• If left-most digit is 1:

  • Flip the bits, and add 1.

  • Convert to base-10, and stick a negative sign in front.

Example: What is in decimal?

• Flip the bits:

• Add one:

• In base-10:

To convert two's complement to a signed decimal number:

• If number is positive: Just convert it to base-2

• If number is negative:

  • Pretend it's unsigned, and convert to base-2

  • Flip the bits, and add 1

Example: What is in two's complement binary?

• In base-2:

• Flip the bits:

• Add one:

1.6 Bias Notation

Idea: Just like unsigned, but shifted on the number line.

• Smallest number: represents .

• Largest number: represents .

To convert from bias to decimal:

• Read as unsigned decimal.

• Add the bias.

Example: Assuming standard bias, what is in decimal?

• , so standard bias is: .

• Read as unsigned: 1

• Add the bias:

To convert from decimal to bias notation:

• Subtract the bias.

• Convert to unsigned binary.

Example: What is in 8-bit biased notation?

• , so standard bias is: .

• Subtract the bias:

• Write in base-2:

1.7 Sign Extension

Leftmost is the most significant bit (MSB).

Rightmost is the least significant bit (LSB).

• Want to represent the same number using more bits than before.

  • Easy for positive numbers (add leading 0's), more complicated for negative numbers.

  • Sign and magnitude: add 0's after the sign bit.

  • One's/Two's Complement: copy MSB.

Example:

• Sign and magnitude:0b1101 = 0b10000101.

• One's/Two's complement: .

2.1 Variable C Types

char: A char takes up to 1 byte.

7 bits are enough to store a char (), but we add a bit to round up to 1 byte since computers usually deal with multiple of bytes.

Typecasting in C: C is a "weakly" typed language, you can typecast from any type to any other.

Union

Unions are similar to structs, but all members share the same memory location, and union only provides enough space for the largest element.

Enum: A group of related integer constants.

CPP (C Preprocessor) Macro

Prior to compilation, preprocess by performing string replacement in the program based on all #define macros.

For example, #define PI 3.14159 => Replace all PI with (3.14159) => In effect, makes PI a "constant".

2.2 Addresses & Pointers

Definitions

• Address: An address refers to a particular memory location.

• Pointer: A pointer is a variable that contains the address of another variable.

• The size of an address (and thus, the size of a pointer) in bytes depend on architecture, e.g., for 32-bit, have possible addresses.

• byte-addressed = each of its addresses points to a unique byte

  word-addressed = each of its addresses points to a unique word

By value vs. By reference

2.3 Array

Declaration & Initialization

A better pattern: single source of truth!

Pointer Arithmetic

• pointer+n: Add n*sizeof("whatever pointer is pointing to")

• pointer-n: Subtract n*sizeof("whatever pointer is pointing to")

Examples

Potential Pitfalls

• Array bounds are not checked during element access

  Consequence: We can accidentally access off the the end of the array!

• An array is passed to a function as a pointer

  Consequence: The array size is lost! Be careful with sizeof()!

• Declared arrays are only allocated when the scope is valid

2.4 Strings

C String: A C string is just an array of characters, followed by a null terminator.

String functions (accessible with #include <string.h>

1. int strlen(char* string):

   Return the length of the string (not including the null term)

2. int strcmp(char* str1, char* str2):

   Return 0 if str1 and str2 are identical (no str1 == str2, since this will be checking if they point to the same memory location!)

3. char* strcpy(char* dst, char* src):

   Copy contents of string src to the memory at dst. Caller must ensure that dst has enough memory to hold the data to be copied.

2.5 Word Alignment

sizeof()

• The C and C++ programming languages define byte as an "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment", most commonly means the number of bites for a char (8 bits).

• sizeof() returns the size in bytes of the type.

• sizeof(char) is always 1!

• Depending on the computer architecture, a byte may consist of 8 or more bits, the exact number being recorded in CHAR_BIT.

• For example, since sizeof(char) is defined to be 1 and assuming the integer type is four bytes long, the following code fragment prints 1,4:

  char c; printf ("%zu,%zu\n", sizeof c, sizeof (int));

Example use:

Struct Alignment and Padding

• Some processors will not allow you to address 32b values without being on 4-byte boundaries.

• Others will just be very slow if you try to access " unaligned" memory.

The actual layout on a 32-bit architecture would be:

sizeof(hello) = 16

Improvement:

sizeof(hello) = 12

2.6 Compilation, Run, Debug & Disassembly

Example

3.1 Bits Manipulation

Types of manipulation

1. Bit-level Manipulation

   • A&B (And): A&B = 1 when both A=1 and B=1

   • A|B (Or): A|B = 1 when either A=1 or B=1

   • ~A (Not): ~A = 1 when A=0

   • A^B (Exclusive-Or (Xor): A^B = 1 when either A=1 or B=1, but not both

   Examples

   int a = 105; // 01101001 int b = 85; // 01010101 printf("a & b = %d\n", a & b); // 65 (01000001) printf("a | b = %d\n", a | b); // 125 (01111101) printf("a ^ b = %d\n", a ^ b); // 60 (0111100) printf("~a = %d\n", ~a); // -106 (10010110, two's complement)

   You can also use this to represent & manipulate sets, do this on char data type, etc.

2. Logic Manipulation

   • View 0 as "False"

   • Anything nonzero as "True"

   • Always return 0 or 1

   • Early termination

   Examples

   unsigned char value1 = 0x41; // Hexadecimal 41 (decimal 65) unsigned char value2 = 0x00; // Hexadecimal 00 (decimal 0) printf("!0x41 = 0x%02X\n", !value1); // Output: 0x00 printf("!0x00 = 0x%02X\n", !value2); // Output: 0x01 printf("!!0x41 = 0x%02X\n", !!value1); // Output: 0x01 printf("0x69 && 0x55 = %d\n", 0x69 && 0x55); // Output: 1 printf("0x69 || 0x55 = %d\n", 0x69 || 0x55); // Output: 1

3. Shift Operations

   • Left Shift (x << y): Shift bit-vector x left y positions

     • Throw away extra bits on left

     • Fill with 0’s on right

     Examples

     

   • Right Shift (x >> y): Shift bit-vector x left y positions

     • Throw away extra bits on right

     • Logical shift: Fill with 0's on left

     • Arithmetic shift: Replicate most significant bit on left

     Examples

     

   • Undefined Behavior: Shift amount < 0 or >= word size

3.2 Multiplication & Division

4.1 Stack

• A stack frame includes:

  • Location of caller function

  • Function arguments

  • Space for local variables

• Stack pointer (SP) tells where lowest (current) stack frame is.

• When procedure ends, stack pointer is moved back (but data remains (garbage!)); frees memory for future stack frames (LIFO-Last In First Out).

Stack Misuse

4.2 Static Data

• Place for variables that persist, and data doesn't subject to comings and goings like function calls, e.g. string literals, global variables.

• String literal example: char * str = "hi".

  char str[] = "hi" is on stack!

• Size does not change, but sometimes part of the data can be writable.

4.3 Code

• Copy of your code goes here, C code becomes data too!

• Does (should) not change, typically read-only.

4.4 Endianness

Endianness

• Big Endian: Descending numerical significance with ascending memory addresses.

• Little Endian: Ascending numerical significance with ascending memory addresses.

4.5 Heap

Stack is not permanent - when the function returns, the memory will be deallocated and turn into garbage.

Dynamically allocated memory goes on the Heap, more permanent and persistent than Stack.

1. malloc(n)

   • Allocates a continuous block of n bytes of uninitialized memory (contains garbage!)

   • Returns a pointer to the beginning of an allocated block; NULL indicates failed request (check for this!)

   • int *p = (int *) malloc(n * sizeof(int))

   • sizeof() makes code more portable.

   • malloc() returns void *; typecast will help you catch coding errors when pointer types don't match.

2. calloc(n, size)

   • void* calloc(size_t nmemb, size_t size)

   • nmemb is the number of the members

   • size is the size of each member

   • Like malloc, except it initializes the meory to 0.

   • Example for allocating space for 5 integers.

     int *p = (int*)calloc(5, sizeof(int));

3. realloc()

   • Use it when you need more or less memory in an array.

   • void *realloc(void *ptr, size_t size)

   • Takes in a ptr that has been the return of malloc/calloc/realloc and a new size.

   • Returns a pointer with now size space (or NULL) and copies any content from ptr.

   • Realloc can move or keep the address same, so DO NOT rely on old ptr values.

4. free()

   • Release memory on the heap: Pass the pointer p to the beginning of allocated block; releases the whole block.

   • p must be the address originally returned by m/c/realloc(), otherwise throws system exception.

   • Don't call free() on a block that has already been released or on NULL.

   • Make sure you don't lose the original address.

4.6 Common Mistakes

Memory error types

• Segmentation Fault: Segmentation fault (often shortened to segfault) or access violation is a fault, or failure condition, raised by hardware with memory protection, notifying an operating system (OS) the software has attempted to access a restricted area of memory (a memory access violation).

• Bus error: Bus error is a fault raised by hardware, notifying an operating system (OS) that a process is trying to access memory that the CPU cannot physically address: an invalid address for the address bus, hence the name.

5.1 IEEE 754 Floating Point Standard

Single precision (SP)

• Sign Bit: 1 means negative, 0 means positive.

• Exponent: IEEE 754 uses "biased exponent" representation.

  • Designers wanted FP numbers to be used even if no FP hardware; e.g., sort records with FP numbers using integer compares.

  • 2's complement poses a problem (because negative numbers look bigger)

  • Bias notation preserves the linearity of value.

• Significand:

  • To pack more bits, leading 1 implicit for normalized numbers.

  • 1 + 23 bits single, 1 + 52 bits double.

  • Always true: 0 < Significand < 1 (for normalized numbers).

  • Bias notation preserves the linearity of value!

  • IEEE 754 uses bias of -127 for single prec, -1023 for double prec.

Example

1 10000001 11100000000000000000000

5.2 Special Numbers

Zero

• Sign bit can be either 0 or 1.

• Exponent is 0.

• Significand is 0.

+0

-0

Infinity

• OK to do further computations with &#x221E;

• Max exponent = 255.

• All zero significand.

+&#x221E;

-&#x221E;

NaN (Not a Number)

• , ,

• Useful for debugging.

• Op(NaN, some number) = NaN

• Max exponent = 255.

• Non-zero significand.

+NaN

-Nan

Denorm Numbers (denormalized numbers)

• Use Exp = 0, Significand &#x2260; 0 to represent very small numbers.

• No leading 0!

• Careful! Implicit exponent = -126 when Exp = 0x00

• Smallest denorm:

• Bigest denorm:

• Smallest norm:

• No uneven gap! Increments by

Conclusion

5.3 Other Representations

• binary64: 11 exponential bits, 52 significand bits

• binary128: 15 exponent bits, 112 significand bits

• binary256: 19 exponent bits, 238 significand bits

• binary 16/fp16: 1/5/10 bits

5.4 Limitations

Two limitations

1. Numbers may get overflow or underflow when expressed in floating points, so rounding occurs and can get unexpected results.

   In addition, the gap between adjacent floating points gets wider, due to increasing exponential number.

   Floating points are denser around 0!

2. FP addition is not associative!

   Example

   float a = 1.0e20; float b = 1.0; float c = -1.0e20; float d = (a + b) + c; float e = a + (b + c); printf("a+b+c = %f\n", d); // 0.000000 printf("a+(b+c) = %f\n", e); // 1.000000

   IEEE FP Rounding Modes

   • Round towards : ALWAYS round "up".

   • Round towards : ALWAYS round "down".

   • Truncate: Just drop the last bits.

   • Unbiased (default mode): Midway? Round to even.