CS250:
Foundations of Computer Systems

Shrideep Pallickara
Office: Room 364, Computer Science
Office Hours:
1:00-2:00 pm Friday
E-mail: compsci_cs250 {aT} colostate.edu
(with the obvious change)
Tel: 970.492.4209



Lecture Coordinates
TTH: 3:30-4:45 pm
Eddy 212

Labs:/Recitations

Teaching Assistants
Office Hours in CSB 120 and Teams
E-mail: compsci_cs250{aT} colostate.edu

Graduate Teaching Assistants
Paige Hansen

Yanye Luther

Santoshkumar Tongli


Undergraduate Teaching Assistants
Emily Cosgriff

Matthew Johnson

Omar Soliman

Objectives:
[1] Summarize basic computer systems concepts
[2] Identify key issues in computer systems

The realm of computer systems is based on binary i.e., all operations are based on 1s and 0s. We will look at the rationale behind this decision and the efficiencies that this choice enables. We will look at properties of binary numbers and how to perform conversions between decimal and binary number representations.

1. Discuss the need for signed number representations
   
2. Explain and compute Two’s and One’s complement number representations of negative numbers.
   
3. Identify challenges in representation of gargantuan/miniscule numbers using binary
   
4. Explain the single-precision and double-precision floating point representations that can be used to represent both gargantuan and miniscule numbers.
   
   

Objectives:

1. Derive truth tables from Boolean functions
   
2. Explain and apply De Morgan’s Laws to transform Boolean expressions
   
3. Explain elementary gates: Or, And, Not, Xor, Nand, and Nor
   
4. Synthesize Boolean functions from Truth Tables
   
5. Prove how all Boolean functions can be constructed using only NAND gates
   

Objectives:

1. Explain how progression of time is modeled and its implication on storage of state
   
2. Identify and explain differences in Combinational and Sequential logic
   
3. Describe the data flip flop
   

Objectives:

1. Explain organization of the memory hierarchy encompassing registers, L1/L2/L3 caches, and main memory.
   
2. Describe memory addressing schemes and how word-aligned memory accesses occur
   
3. Synthesize concepts of cache lines and differences in direct-mapped and associative caching schemes
   
4. Design programs that identify and profile the impact of different caching based either on temporal or spatial locality
   

Computers designed over the past 70 years or so are all based on the von Neumann architecture. In this module, we will look at several elements that comprise this architecture. Also included in this module is the notion of the stored program concept – one of the most foundational ideas in computer science. The module will also cover aspects relating to bus architectures, Moore’s law, and Dennard’s scaling. A key concept that we also look at in this module is Memory-Mapped I/O which allows a computer system to interoperate with a plethora of Input/Output (I/O) devices.

Objectives:

1. Explain the stored program concept
   
2. Identify different constructs within the von Neumann architecture and how they have influenced design of computer systems
   
3. Explain how memory mapped I/O allows the computer system to reconcile diverse I/O devices
   
4. Explain differences between the Harvard architecture and the von Neumann architecture
   
5. Explain the role buses play in the von Neumann architecture.
   

Programs expressed in high-level languages need to be converted to a representation that the computer system can execute. This includes translating the semantics of higher-level languages into those that the computer system can process. We will be looking at characteristics of machine languages both binary and symbolic. We will also be looking at the notion of Instruction Set Architectures (ISAs) and we will be looking at different generations of the x86 ISA and ARM.

Objectives:

1. Explain difference between binary and symbolic versions of machine language.
   
2. Identify the role of ISA as a model for how computations are performed.
   
3. Explain evolution of the x86 ISAs over time.
   
   

Objectives:

1. Explain the two-tiered compilation model in virtual machine environments
   
2. Explain the role (and interactions between) stacks, heaps, and stack frames
3. Describe the stack machine
   

In this module, we will be discussing some of the foundational constructs in communications. This includes issues such how data are encoded prior to transmission. We explore the two different network types (circuit switched and packet switched) and how they enable multiplexing (or sharing) of the networking architecture.  We also explore a key issue of encapsulation that plays a foundational role in networked communications.

Objectives:

1. Describe data encoding and representation mechanisms in communications
   
2. Explain differences in circuit switched networks and packet switched networks
   
3. Identify how multiplexing of data can occur over shared networks
4. Understand organization principle of protocol layers and encapsulation
   

This module is the centerpiece of our discussions in networking. We will be looking at the Internet Protocol stack. We will be explored the core layered protocol stack. Our discussions will look at the core protocol, Internet Protocol, underpinning the internet. Our explorations cover both IPv4 (the original, and currently dominant) and IPv6 (the next generation) versions of the protocol. We will look at reliable (TCP or the Transmission Control Protocol) and unreliable communications (UDP or the User Datagram Protocol).

1. Identify the rationale for layering and the role it plays in encapsulation
   
2. Explain fragmentation and reassembly in IP networks
   
3. Explain the inner workings of IPv4 and IPv6 alongside key architectural differences that exist between them
   
4. Identify key differences in connection-oriented and connectionless communications
   
5. Explain key concepts underpinning TCP such as congestion control, flow control, and the sliding window protocol including setup and teardown of TCP connections.
   
6. Design and develop programs that leverage networked communications.
   

1. Describe how network address translations (NATs) work
2. Highlight the need and rationale for private addresses
3. Distill core ideas in DNS and how network addresses are resolved

In this module, we look at a key data structure for one of the most important I/O device: stable storage. We describe the key differences between in-memory and on-disk data structures. To ensure that our discussions are self-contained we first start with linear scan that we then improve by pruning search spaces using binary search. We discuss the notion of dynamic data structures that adapt to contents of the data items. Next, we cover a popular in-memory data structure, Binary Search Trees (BSTs). We then cover one of the most foundational data structures for storage systems: B-Trees. In particular, B-trees are data structures that are designed to align with how data access and transfers (block-based) take place in storage systems. We highlight both the similarities and key differences between BSTs and B-Trees. Issues such as insertions, deletions, merges, and balancing in B-Trees are discussed as well. We complete our discussions on B-Trees with variants such as B*-trees and B+-Trees.

Objectives:

1. Identify how binary search improves upon linear scan
2. Explain key concepts underlying dynamic data structures
3. Design and develop programs that implement BSTs including insertions, deletions, and search
4. Design and develop programs that implement B-Trees including insertions, deletions, and search
   
   

Graphics processing units (GPUs) are used extensively in gaming and AI/ML (Artificial Intelligence/Machine Learning) applications. In this module, we will explore GPS and contrast them with CPU based systems. A key emphasis here is to identify the specific types of problems that GPUs are particularly well-suited for. We will explore the issue of memory locality and cache coherency in both GPU and CPU based systems. Notably, CPUs and GPUs work in tandem with each other and workloads that effectively target them will see considerably improved performance.

Objectives:

1. Explain the role of the GPU in the computing ecosystem
2. Identify how the GPU differs from (and complements) the CPU