# CS351 - Computer Organization

## Binary Multiplication

### Binary Multiplication table

Multiplication in binary is similar to multiplication in decimal, however you're only multiplying with 0 or 1, which simplifies the math considerably.

* 0 1
0 0 0
1 0 1
• Note that 0 times anything is always 0 (just in case you forgot.)
• Note that any value times 1 is the same as the original value.

Given `A` (some value), times `0b1010`:

``````     A
x 1010
------
0  (0 * A == 0)
A0  (1 * A == A (left shifted by 1))
000  (0 * A == 0 (left-shifted by 2, but still just 0))
+ A000  (1 * A == A (left-shifted by 3))
------
A0+A000``````

### Algorithm:

``````result ⟵ 0
while (N ≠ 0):
if (N & 1):
result ⟵ result + A
A ⟵ A << 1
N ⟵ N >> 1``````

From the algorithm it should be clear that the result should have at least as many bits as A and N combined to prevent a multiplication overflow. It should also be obvious that N should be unsigned to prevent the loop from running forever (assuming that it is right shifted by the implementation.)

## dividing in binary?

• Left as an exercise to the student.

# Conversion of ASCII to an integer

A sequence of characters representing an integer can be converted to an actual value by computing the numeric value for each digit and then adding/shifting the digit into its position within the integer value.

### Algorithm

``````digits ⟵ "0123456789ABCDEF"
base ⟵ The base of the number system (i.e. 10, 2, 16, etc)

str ⟵ some string of characters representing a integer value
value ⟵ 0
i ⟵ 0
while ( str[i] ≠ end of string ):
value ⟵ value ∙ base
str[ i ] ⟵ uppercase version of str[i] // (optional)
value ⟵ value + (index of str[i] in digits)
i ⟵ i + 1``````

### Example

``````value = 0

┌─────┬─────┬─────┬──────┐
str = │ '3' │ '2' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^
value = 0 * 10      == 0
value = 0 + 3       == 3

┌─────┬─────┬─────┬──────┐
str = │ '3' │ '2' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^
value = 3 * 10      == 30
value = 30 + 2      == 32

┌─────┬─────┬─────┬──────┐
str = │ '3' │ '2' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^
value = 32 * 10     == 320
value = 320 + 6     == 326
``````

# Integer to ASCII (decimal, hex, octal, binary)

``````digits ⟵ "0123456789ABCDEF"

str ⟵ array of characters large enough to store the number after conversion
i ⟵ index at end of str
str[i] ⟵ '\0'

repeat:
d ⟵ value % base
i ⟵ i - 1
str[ i ] ⟵ digits[ d ]
value ⟵ value / base
until ( value = 0 )
``````

### Example

``````value = 326

┌─────┬─────┬─────┬──────┐
str = │ ' ' │ ' ' │ ' ' │ '\0' │
└─────┴─────┴─────┴──────┘
^

d = 326 % 10        == 6

┌─────┬─────┬─────┬──────┐
str = │ ' ' │ ' ' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^

value = 326 / 10    == 32
d = 32 % 10     == 2

┌─────┬─────┬─────┬──────┐
str = │ ' ' │ '2' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^

value = 32 / 10     == 3
d = 3 % 10      == 3

┌─────┬─────┬─────┬──────┐
str = │ '3' │ '2' │ '6' │ '\0' │
└─────┴─────┴─────┴──────┘
^

value = 3 / 10      == 0
stop
``````

# Memory

## Memory types:

• Cannot be written to (obviously)
• "Non-volatile" - maintains its data even after the power is removed.
• Forms:
• Mask ROM - Can never be changed after creation
• Erasable Programmable Read-Only Memory (EPROM) - Electrically programmable, but erased via ultra-violet light. Usually requires special hardware to perform the programming.
• Electrically Erasable Programmable ROM (EEPROM) - Like EPROM, but erasable via special programming signals.

RAM - Random Access Memory

• Usually "volatile" in nature, i.e. loses its state when the power is removed.

• Types:

• Static RAM (SRAM) - memory built from latching "flip-flop" circuitry. Does not require being periodically "refreshed" to maintain its state. Typically the fastest type of memory, it often is used for CPU cache memory.

• Dynamic RAM (DRAM) - memory that uses a capacitor alongside each bit to store a charge to maintain the state of the the bit. The capacitor must be periodically "refreshed" by either reading or writing the memory. To insure that all memory gets refreshed some of the time that the memory is available is reserved to perform these refresh operations, causing the memory to be slower overall to SRAM.

• Each bit in SRAM requires up to 6 transistors whereas a DRAM bit requires a single transistor and capacitor.
• Non-Volatile RAM (NVRAM) - Currently typically used as storage, since it is over-all slower than RAM and has large write sizes (a block of data must be re-written to change a single byte,) however as the technology improves it may more usable as a primary or secondary memory.

• Synchronous Dynamic RAM (SDRAM) - DRAM that uses an external timing signal to coordinate memory transactions.

• Double Data Rate SDRAM (DDR SDRAM) - Doubles the effective bandwidth by allowing two reads/writes per clock cycle (uses both the rising and falling edge of the clock to synchronize transfers.)

• DDR2,3,4,5 - Doubles the data rate again

• GDDR - GDDR6 - Graphics DDR - Memory designed for high-bandwidth graphics processing units (GPUs).

• High Bandwidth Memory (HBM) - 3D memory (stacked layers of SDRAM) that can be placed much closer to the processing unit (usually GPU) to increase bandwidth considerably.

## Memory units

• bit - The smallest unit of memory, which is in one of two states, either electrically low or high which is usually assigned values 0 or 1.

• nibble - A sub-division of 2-7 bits within a byte. 2 bits is typically called a bit-pair however.

• byte - The smallest unit of addressable memory which is typically composed of a group of 8 bits.

• word - Two contiguous bytes (16 bits)

• double word - 4 contiguous bytes (32 bits)

• quad word - 8 contiguous bytes (64 bits)

## Addressing and Byte Order (Endianness)

Every byte in memory has a numeric address. The amount of addressable memory depends on the size of the CPU's address bus (measured in bits) which represents the one half of the CPUs connection to memory and/or devices.

When the CPU requires more than one byte of memory, such as for an integer, which is composed of 4 consecutive bytes, then the address of the integer is the address of the first byte of that integer (i.e. the byte with the lowest address.)

In Big-endian systems the first byte is the most significant, followed by the next most significant, and so on until the last byte which is the least significant byte. Network byte order is also big-endian.

``````    a    a+1  a+2  a+3
┌────┬────┬────┬────┐
│ 1F │ 2C │ 50 │ 23 │
└────┴────┴────┴────┘``````

`a` represents the starting address of the integer. In both above and below the number being represented is `0x1F2C5023`

In Little-endian systems (such as x86) the least significant byte is first, increasing in significance until the last byte which is the most significant.

``````    a    a+1  a+2  a+3
┌────┬────┬────┬────┐
│ 23 │ 50 │ 2C │ 1F │
└────┴────┴────┴────┘``````

Some systems (some ARM, RISC-V, PowerPC) are Bi-endian, and can interpret numbers both ways, although the direction is often decided at boot time or via hardware and cannot be changed while running.