Spring 2024 · Undergraduate

C S 429

Computer Organization and Architecture

In-person · Unique 50855, 50860, 50865, 50870, 50875, 50880, 50884

This page is intentionally shallow; most links below point to UT-internal resources for the current offering.

Personnel

Instructor: Dr. Siddhartha Chatterjee.
TAs: see the Canvas page.

Office Hours

See the Canvas page.

Course Overview

C S 429 is the first course in the systems core sequence required of all computer science majors at UT. It describes computer systems from a programmer's perspective, at a fairly low level of abstraction. It is a prerequisite for C S 439 (Principles of Computer Systems, aka “OS”: the second systems core course) and C S 331 (Algorithms and Complexity, aka “Algo”: the second theory core course). It also serves as a foundation for upper-division courses on compilers, networks, operating systems, and computer architecture, where a deeper understanding of systems-level issues is required.

Prerequisites

The following coursework with a grade of at least C- in each:

Discrete Math for Computer Science: C S 311 or C S 311H.
Data Structures: C S 314 or C S 314H.

Topics

The course is organized into one language module and five additional content modules.

Programming in C in a Linux environment. The C programming language. The Linux command-line (shell) environment. Standard libraries. Programming tools: compilers, build systems, debuggers, version control tools. Understanding requirements and exploring design choices. Writing clean code. Students will write three reasonably complex programs in C in a Linux shell environment and integrate them into pre-existing modules such as test harnesses and simulators.
Representing and manipulating data. Binary encodings of, and basic operations on, basic data types: integers, floating-point numbers, and characters. Unicode and UTF-8. Derived data types: arrays, structures, unions, functions, pointers. Data alignment.
Machine-level representation of programs. Machine-level encoding and execution of programs written in high-level programming languages. The Armv8 A64 instruction set architecture (ISA). Data access instructions, arithmetic and logical operations, non-sequential control transfer, procedure call/return. Stack and heap disciplines for memory management. Code generation for C constructs. Techniques for explicit memory management.
Linking. ELF files: object modules, executables, and shared objects. Techniques for static linking: symbol resolution, relocation, and patching. Techniques for dynamic linking: shared segments, GOT, PLT, lazy binding. Run-time programmatic linking of libraries.
Processor architecture and implementation. Basics of logic design. Sequential and pipelined implementations of a representative subset of the A64 ISA. Dependences and hazards. Forwarding, stalling, squashing. Pipeline control. Branch prediction. Pipeline performance equation.
Storage system architecture and performance. Volatile and non-volatile storage technologies. Locality of reference. Memory hierarchy. Structure and behavior of caches. Memory performance equation. Secondary storage and I/O. MMIO and DMA.

This is a programming-heavy course, with an emphasis on low-level systems programming. The primary programming language for this course is C. We will also use A64 assembly language extensively throughout the course.

Textbooks and Materials

The following books are recommended but not required.

Computer Systems, A Programmer's Perspective, Third Edition, by Randal E. Bryant and David O'Hallaron. Pearson, 2016. ISBN-13: 978-0-13-409266-9.
Computer Organization and Design: The Hardware/Software Interface, ARM® Edition, by David A. Patterson and John L. Hennessy. Morgan Kaufmann, 2017. ISBN: 978-0-12-801733-3.
The C Programming Language, Second Edition, by Brian W. Kernighan and Dennis M. Ritchie. Prentice Hall, 1988. ISBN: 0-13-110326-8. The classic K&R book — it should be in the library of anyone who programs in C.

In addition, we will be referencing official manuals and original papers, soft copies of which will be provided.

Weekly Schedule

Week	Lectures
1	Syllabus. Introduction to C and Linux. Linked lists in C. Huffman coding in C.
2	Values and representations. Bit technologies. Codebooks. Weighted codes. Positional codes. Octal and hexadecimal notation. Signed representations. Number wheel. Conversion, expansion, truncation. Boolean operations. Shifts. Word size.
3	Labor Day. No class. Byte ordering. Integer arithmetic: addition, subtraction. Multiplication, division. Special cases. Ripple-carry adder. Manipulating integer representations: basic techniques.
4	Manipulating integer representations: advanced techniques. Floating-point: representation. Floating-point: operations. Dynamic memory management: basic techniques.
5	Dynamic memory management: advanced techniques. Character data. ASCII, Unicode. UTF-8 encoding. Records and variant records: `struct` and `union`. Arrays. Pointers. Data alignment.
6	Introduction to ISAs. von Neumann and Harvard architectures. AArch64 state and programming model. Operand specifiers: immediate, register, memory. Data transfer instructions. ALU instructions.
7	Code generation for basic and derived types. Control transfer instructions. Code generation for two-way branches and iterative constructs (`do`, `while`, `for`). Code generation for multi-way branches (`switch`) and structured exits (`break`, `continue`).
8	Procedural abstraction. Call/return instructions. Activation records. Runtime stack. Managing architectural register state. AArch64 ABI.
Spring Break
9	Binary file formats: ELF. Runtime memory map. Static linking: symbol resolution, relocation, patching. Dynamic linking: shared segments, GOT. PLT and lazy binding. Programmatic run-time linking.
10	Digital logic. Combinational building blocks. Buses. Building an ALU. Maintaining state. Latches, flip-flops. Clocks. Sequential circuits. FSMs.
11	Single-cycle implementation of A64 subset. Data and control paths. Retiming. Principles of pipelining. Naïve pipelined implementation. Correctness issues.
12	Dependences and hazards. Mitigating hazards: stalling, bubbling, squashing, forwarding. Hazard-free pipelined implementation. Pipeline performance equation (PPE). Exception handling in pipelines.
13	Volatile and non-volatile storage technologies. Towards a storage hierarchy. Structure of caches: ABC model. Behavior of caches.
14	Performance of caches: 3C model. Memory performance equation (MPE). Average memory access time (AMAT). DRAM cells, chips, modules. SDRAM controller. ECC. HDD: structure, behavior, performance. Flash and SSD: technology, structure, performance, issues. Buses, MMIO, DMA.