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
Emilie Beck

Phil Hopkins

Yunik Tamrakar

Undergraduate Teaching Assistants
Omar Soliman

Benito Encarnacion

Parker Jones

Alberto Marmolejo-Daher

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
   

Think of communication networks as enabling conversations at lightning speed. In this module, we’ll unravel some of the fundamental ideas that make these conversations possible. First, we’ll examine how data is prepared for its journey: how raw information is encoded before being sent across a network. Then, we’ll dive into the two main types of networks: circuit-switched and packet-switched. We will also explore how multiple conversations can share the same infrastructure, a concept known as multiplexing. Finally, we’ll explore one of the most elegant principles in networking: encapsulation. Much like the way letters are placed in envelopes, addressed, and sent through layers of postal systems, encapsulation ensures that messages travel efficiently and reach the right destination. Understanding these core ideas will give us a deeper appreciation for the choreography that underpins modern communication.

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 at the heart of our discussions on networking, where we unravel the elegant design of the Internet Protocol (IP) stack. At its core is a layered architecture that keeps the internet running smoothly. We’ll examine the foundation of it all -- the Internet Protocol itself -- exploring both IPv4, the workhorse of today’s internet (and yesteryears), and IPv6, its forward-looking upgrade designed for the future. We’ll also contrast two very different approaches to communication: TCP, which ensures messages arrive reliably and in order, and UDP, which trades reliability for speed. Together, these ideas reveal the underpinninggs of every connection, from web browsing to video streaming.

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 GPUs 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