Resources

Nand2Tetris

Computer

Rapaport (2018) provides a more explicit characterization of a computational system defined as any “physical plausible implementation of anything logically equivalent to a universal Turing machine”.

[1] N. Angius, G. Primiero, and R. Turner, “The Philosophy of Computer Science (Stanford Encyclopedia of Philosophy),” Stanford.edu, 2013. [Online]. Available: https://plato.stanford.edu/entries/computer-science/. [Accessed: 30-Aug-2021]

Examples are:

Video game console.

Consoles.

Story

https://www.youtube.com/watch?v=zXPiqk0-zDY&ab_channel=FromScratch

https://www.computerhistory.org/timeline/

https://computerhistory.org/

Why do computers use binary?

Because electricity with 10 states is not the easy way. Please try to sum two numbers with electricity and ten states. Boolean algebra. Discrete signal processing.

Nibble

Why is random access memory called random?

“Random” means that the data does not have to be stored or read in any particular sequence. Random means lacking a definite plan, purpose, or pattern. Historically called random access memory because any data word can be accessed as easily as any other.

https://www.youtube.com/watch?v=Rc6qqqFZisI&ab_channel=AdamGaweda

Computer graphics and related stuff in modern computers

Fonts are vectors when you have an operating system they are saved as files in a special location in the storage device in order to show something on the screen, you need to pass by GPU. . But, also fonts and other graphical stuff are stored in the firmware (e.g. EFI or BIOS) itself.

Fonts, UNICODE, UTF-8, ASCII, and others.

All are bits. But it is depending on who receives that word and then executes an operation or another one.

PRINTF(01001100) -> Send to Graphics Processing Unit -> PRINT A on Screen

ADD(01001100,01001100) -> Send to Proccesor -> 76 + 76 and send in register. 

Levels of the answer:

Compiler, Assembler, Binary, Hardware, Formal languages.

https://stackoverflow.com/questions/41993429/what-s-the-difference-between-a-pointer-to-an-int-and-a-pointer-to-a-pointer-to

http://wiki.icmc.usp.br/images/4/42/Aula_20_-_memoria_harris_book.pdf

Where is the ASCII table located in the memory? Which type of memory do we use to store it?

How did computers understand ASCII bit? For example, 01001100 is L, not 76. Does a computer store integers according to ASCII?

CISC vs RISC

MIPS 32

MARS MIPS simulator - Missouri State University. (2017, December 07). Retrieved from https://courses.missouristate.edu/KenVollmar/MARS

https://gist.github.com/sanchezcarlosjr/f19edbe47ad48b93b79800a285911a81

https://godbolt.org/z/Tzoj81h6e

https://en.wikibooks.org/wiki/MIPS_Assembly/MIPS_Details

https://electronics.stackexchange.com/questions/136916/use-of-at-register-in-mips

Metrics units

GiB or GB $2^{10}$

Gbps $10^9$

Type Space

1 ASCII char is 1 byte

Field-programmable gate array

Hardware description language

Memory

Memory hierarchy.

When people say “memory” normally refers to RAM. However, today we have a memory hierarchy. We explain the memory layout in the RAM, register behavior, and communication between the RAM and the processor using MARS.

Word.

Bit numbering

https://www.youtube.com/watch?v=jhErugDB-34

https://www.youtube.com/watch?v=RvFRCDoj6JI

(LSB) Little Endian, (MSB) Big Endian.

LSB first.

MSB first.

Example. 0x010000…00 (32-byte one, LSB first)

The value 0x010000…00 is a hexadecimal representation of a 32-byte (or 256-bit) number where the least significant byte (LSB) comes first (little-endian format).

In little-endian format, the least significant byte is stored in the smallest address and hence comes first. So 0x01 is the least significant byte, and the rest of the bytes (31 of them, in this case) are 0x00.

If this was a big-endian format (most significant byte first), it would represent a very large number with a value of 1 followed by 31 zero bytes.

But as a little-endian format, it represents a small number because 0x01 is the least significant byte. It means the number is just 1 in decimal.

For comparison:

• Little-endian: 0x010000...00 (LSB first) represents 1 in decimal.

• Big-endian: 0x010000...00 (MSB first) would represent a very large number (about 1.16e+77 in decimal).

Consider a 4-byte (32-bit) integer value of 1. In hexadecimal representation, it is 0x00000001.

• In little-endian (LSB first), this would be stored or transmitted as 0x01000000.

• In big-endian (MSB first), this would be stored or transmitted as 0x00000001.

Consider a 4-byte (32-bit) integer value of 254. In hexadecimal representation, it is 0x000000FE.

• In little-endian (LSB first), this would be stored or transmitted as 0xFE000000.

• In big-endian (MSB first), this would be stored or transmitted as 0x000000FE.

Arrays, Structs (or classes), numbers, and chars. Offset.

List.

Type.

Construction.

Address vs Content.

Intel® 64 and IA-32 Architectures Software Developer Manuals. (2020, December 22). Retrieved from https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

Little Endian vs Big Endian

TODO: In the model, we must include the stored program, the “word” concept, the “program to process” process, an array, a list, and a tree. We must include a model with electronic.

A word is a sequence of $O(w)$ bits where a processor can operate with them in constant time $O(1)$.

How many bits does a WORD contain in 32/64 bit OS respectively? (2023, January 15). Retrieved from https://stackoverflow.com/questions/5295903/how-many-bits-does-a-word-contain-in-32-64-bit-os-respectively

So, suppose we say a word of 64 bits, it means you ca

Learn MIPS Assembly in Y Minutes. (2023, January 15). Retrieved from https://learnxinyminutes.com/docs/mips

Memory Layout —RAM layout

data
text
heap
stack

Heap Memory

https://stackoverflow.com/questions/2308751/what-is-a-memory-heap

https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS2/html/HeapMem.html

Memory in action

Where do you locate data in memory? What looks like a memory layout with different types?

Integer

The most basic data type is an int. Now, we save a byte 8 bits, so the largest decimal you can save in a byte is $2^8-1=255$. You are going to experiment with it .data, so you don’t need registers.

.data
constant: .byte 97

Assemble it and now you can observe the memory layout in the execute tab.

Congratulations! You are allocated a byte with the value 97 at the address 0x1001000.

Ok, maybe you are thinking that interesting happened in boundaries. That is a negative number and a considerable number —a number is out-of-range for a signed value. Managing negative numbers means you have to deal with 2 complements. It means when you allocate a byte with signed values, you can express $2^7-1=127$ positive numbers and you can express $255-2^7-1=126$ negative numbers; therefore, a big number happened when you have a decimal number greater than $127$ and less than 256 ($128\le x\le255$) —if you express a number greater than 255 your program will have strange behaviors.

127 case.

.data
var1: .byte 127

-1 case.

.data
var1: .byte -1

128 case.

.data
var1: .byte 128

Word, byte, and word alignment TODO Registers.

But, what happened if you want to save a word?

.data
var1: .word 100
var2: .word 300
var3: .word 140
var4: .word 5000
var5: .word 10000
var6: .word 20000
var7: .word 30000
var8: .word 60000
var9: .word 70000

.data
var1: .word 100
var2: .word 300
var3: .word 140
var4: .word 5000
var5: .word 10000
var6: .word 20000
var7: .word 30000
var8: .word 60000
var9: .word 70000

And array?

.data
var1: .word 1 2 3 4 5 6 7 8

You want fill out the memory

.data
var1: .word 1 2 3 4 5 6 7 8
var2: .word 1 2 3 4 5 6 7 8
var3: .word 1 2 3 4 5 6 7 8
var4: .word 1 2 3 4 5 6 7 8
var5: .word 1 2 3 4 5 6 7 8
var6: .word 1 2 3 4 5 6 7 8
var7: .word 1 2 3 4 5 6 7 8
var8: .word 1 2 3 4 5 6 7 8
var9: .word 1 2 3 4 5 6 7 8
var10: .word 1 2 3 4 5 6 7 8
var11: .word 1 2 3 4 5 6 7 8
var12: .word 1 2 3 4 5 6 7 8
var13: .word 1 2 3 4 5 6 7 8
var14: .word 1 2 3 4 5 6 7 8
var15: .word 1 2 3 4 5 6 7 8
var16: .word 1 2 3 4 5 6 7 8

And what happened if you run out of memory?

Char

.data
constant: .byte 'a'

String

.data
var1: .asciiz	"Hello"

Float

Array

.data
var1: .word 0x20FF 0x100019AF '0'

Bit Twiddling Hacks or Bit manipulation

https://graphics.stanford.edu/~seander/bithacks.html

https://homolog.us/blogs/bioinfo/2014/12/04/the-entire-world-of-bit-twiddling-hacks/

https://www.fit.vutbr.cz/~ibarina/pub/bithacks.pdf

https://news.ycombinator.com/item?id=17043082

https://web.stanford.edu/class/archive/cs/cs107/cs107.1216/lectures/03/Lecture03.pdf

Builtin functions of GCC compiler

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

• __builtin__popcount(Hamming weight)

• __builtin_parity

• __builtin_clz

Worked examples

• Make a program in C++ that checks if the Sentence Is Pangram with no set/map.

  bool checkIfPangram(string sentence) {
          int i = 0;
          int set = 0;
          while(i<sentence.size() && set != 67108863) {
              int element = sentence[i]-97;
              set = set | (1 << element); // 0, 1, 11, 111, 111, 1111, ....  
              i++;
          }
          return set == 67108863; // 11111111111111111111111111
  }

• Make a program in C++ that detects if a number is the power of 2 with no modulus.

  bool checkIfPowerOf2(int x) {
         return x&1 == 0;
  }

• Make a classic Tic Tac Toe game that works with bit-wise operators. The board should be an integer or hex too.

  Algorithm for Determining Tic Tac Toe Game Over. (2022, October 01). Retrieved from https://stackoverflow.com/questions/1056316/algorithm-for-determining-tic-tac-toe-game-over

https://cs.wellesley.edu/~cs240/s17/slides/bits-handout.pdf

Getting 32 bit words out of 64-bit values in C/C++ and not worrying about endianness. (2023, January 15). Retrieved from https://stackoverflow.com/questions/2194310/getting-32-bit-words-out-of-64-bit-values-in-c-c-and-not-worrying-about-endian

Computer hierarchy

Programmer’s point of view

Domain language level

Assembly language level

Operating system machine level

Instruction set architecture level (ISA level)

Microarchitecture level

Digital logic level

User’s point of view

Application software

Operating system

EFI/BIOS

Firmware

Hardware

What is the first process? General boot process.

A typical boot process for commercial computers.

1. Motherboard

2. Firmware. BIOS/EFI. Bootloader. Protected mode.

3. Kernel.

4. User interface.

5. User Applications.

So, our first problem is starting after firmware.

GDT Tutorial

CPU

We know by memory hierarchy the CPU has memory, it has registers.

Datapath

Special extensions in modern x86 CPUs

AVX

SHA

MMX

RdRand

Worked example

Create a program in an assember that calls some modern instruction

SHA

GPU

GPGPU

OpenCL

NVDIA and amd

CUDA

nvcc

opengl

vulkan

TPU

NPU

Procedures & The Stack

https://courses.cs.washington.edu/courses/cse351/16sp/lectures/06-procedures_16sp.pdf

Computer performance measurement

FLOPS

Bits

https://www.youtube.com/watch?v=jAu0oyxsP20&ab_channel=FrankStajanoExplains

Real Assembly. Systems based on microprocessors.

1. El universo digital del IBM PC, AT y PS/2. Ciriaco García de Celis, documentación

gratuita en la red

2. Los microprocesadores Intel. Barry B. Brey, Ed. Prentice-Hall

3. IBM PC & XT, Assembly Language. Leo. J. Scalon, Ed. Brady

4. Arquitectura, programación y diseño de sistemas basados en microprocesadores

(80x86/80186/80286). Yu-Cheng Liu y Glenn A. Gibson, Ed. Anaya

Building the computer

mortbopet. "VSRTL." GitHub, 27 Jan. 2023, github.com/mortbopet/VSRTL.

Computing with Register Machines by SICP.

Nöding, Florian. "How a CPU works: Bare metal C on my RISC-V toy CPU." 26 Jan. 2023, florian.noeding.com/posts/risc-v-toy-cpu/cpu-from-scratch.

Clock

Computer arithmetic with circuits in a datapath

Next steps

Implementation of mathematical functions in computer (no lib).

0.9 Von Neumann Model? Mauchly model?

This was teamwork, then We called EDVAC Model from “First Draft of a Report on the EDVAC”, no Von Neumann Model.

0.8 Turing model

0.10 Computer components

Store program

Evans, D. C. A. (2017, October 10). Stored Program Computer. Youtube. Retrieved from https://www.youtube.com/watch?v=j3XikkuFDSk&ab_channel=DrCraigA.Evans

References

At ieee dot org, B. K. k. (2020, August 25). Programmed Introduction to MIPS Assembly Language. Retrieved from https://chortle.ccsu.edu/assemblytutorial/index.html#part1

TODO

Lague, S. (2020, November 16). Exploring How Computers Work. Youtube. Retrieved from https://www.youtube.com/watch?v=QZwneRb-zqA&t=4s&ab_channel=SebastianLague

Overflow