This course gives an introduction into the design of digital circuits and systems, including design at the gate level and design of more complex systems at the register transfer level, and into the organisation and design of modern computer systems, in particular the efficient interplay of hardware and software in processor desig
After attending this course, students are able to
- describe the design flow for digital systems from specification to realisation
- explain and apply models and methods of Boolean algebra and automata theory to digital systems design
- realise digital designs of medium complexity
- analyse and evaluate digital designs with respect to given design goals
- describe the organisation of modern computer systems
- describe and apply basic design principles guiding computer systems design
- analyse and evaluate computer systems with respect to performance and cost metrics
- create simple assembly language programs
High-level structure of lecture and exercises
- Introduction to digital design: signals, continuous vs. discrete, analog vs. digital, digital and binary systems
- Models at the logic level: switches, gates, Boolean algebra, Boolean functions, representations for Boolean functions
- Combinational logic design: combinational circuits, canonical representations, complete gate sets, design goals, minimisation of two-level (K diagram) and multi-level logic
- Sequential logic design: models of time, latches, flip-flops, register, counters, automata (finite state sets, deterministic, complete), structures of sequential circuits (Mealy, Moore), equivalence, reduction, state minimisation, state encoding
- Binary numbers and codes: positional notation systems, unsigned and signed fixed point numbers, floating point numbers, basic arithmetic, binary codes
- Register transfer level: combinational elements (multiplexer, encoder, ...), sequential elements (registers, memories), arithmetic components (add/sub/multiply/divide), controller and data path, register transfer level design steps and examples
- Technological realisation: physics basics, semiconductors, transistors in MOS structure, realising switches and gates in MOS technology, design and manufacturing of integrated circuits, Moore's law, trends in nano-electronics
- Introduction to computer architecture: classes of computers, trends in technology and cost
- Instruction set architecture and assembly language: MIPS instruction set and assembly programming, the roles of compiler, linker, assembler and loader, classifications of instruction set architectures, IA-32 architecture
- Performance evaluation: processor performance equation, contributing factors, performance evaluation metrics, Amdahl's law
- Processor design: MIPS datapath and controller, single-cycle implementation, multi-cycle implementation
- Pipelining: principle and achievable speedup, MIPS datapath and controller for pipelining, structural hazards, data hazards (forwarding), control hazards (delay slots, static and dynamic branch prediction)
- Memory hierarchy: technology trends, direct mapped and set-associative caches (mapping and finding cache blocks, replacement strategies, writing blocks to memory), processor performance including the memory hierarchy, memory organisation, basic cache optimisation techniques, virtual memory (brief introduction), translation look-aside buffer, case studies for memory hierarchies
- Advanced concepts: deep pipelining, pipeline scheduling, multiple issue processors (superscalar, VLIW)
- Pencil and paper exercises: Boolean algebra, logic functions, design of combinational and sequential functions, number representations and codes, arithmetic components, register transfer level design, processor performance, processor design, memory hierarchies
- practical MIPS assembler programming
This module is a high-level summary of software-oriented systems lectures as taught in many typical CS Bachelor programs; typical examples would be Introduction to Operating Systems, Introduction to Computer Networks, or a Distributed Systems class.
The emphasis is on practical aspects, enabling participants to work productively closer to the systems interface. This entails both practical work (using, e.g., a shell, writing BASH scripts, ...) as well as programming work (using, e.g., system-level OS APIs like the socket interface or the process management interfac
- Concurrency vs. parallelism; processes, threads. Programming abstractions for that.
- Simple schedulers: round robin, FCFS, MLFB
- Coordination techniques: why are they needed (race conditions, concurrent access), examples for such techniques (lock variable, semaphore, condition variables)
- Deadlock as a phenomenon; simple techniques for avoidance
- Networking: shared medium with MAC protocol, Internet and routing, transport (TCP, semantics).
- Distributed systems: client/server. Server models (one process, multiple threads, ...). Programming models. Enable participants to write a simple web application.
- Linux command line interface, bash with simple bash programming
- Compile a Linux kernel, kernel modules (monolithic kernel vs. module-based kernel?) -- this is optional.
- Makefiles: what are they, why needed
- Simple concurrent/parallel programming. Eg. matrix multiplication with varying number of threads
- Optionally: Write a very simple scheduler in a simulation environment
- A little bit of C, a little bit of Python (needed for the web framework).
- Socket programming
- Writing a SIMPLE client/server application using sockets (ECHO)
- Optionally: Web frameworks: use a simple Web framework to build a web application.
High-level structure of lecture and exercises
Rough lecture schedule
- Execution model of a program, context of a processor/memory, instruction pointer in CPU. (Skip: Caching) Minimal ideas about assembler -> simplified
- Calling a subroutine, from there to interrupt handling. notion to switch between execution threads. Notion of threads and concurrent, interleaved execution. Thread table. Programming models.
- introduction to C
- Generalize to processes: protection between executing threads. Explain requirements for memory management. Protection context. Process switches. Process table. Process states. Blocking as a new notion for processes. Programming models, again.
- Scheduling: goal, simple mechanisms. Preemption yes/no.
- Coordination mechanisms: locks, semaphores. Integration with process management.
- Programming patterns with semaphores. critical section. producer/consumer. reader/writer (only one, best focus on reader/writer). (time permitting: priority inversion., concept of a deadlock
- Memory management. Start from simple swapping, relocation, address indirection, virtual memory. Address translation.
- Virtual memory: paging strategies. Understand relation to process management. Time scales!
- NEtworking 1: packets, shared medium, MAC protocols.
- Networking 2: Internet.
- Networking 3: Transport layer, basic ideas about TCP's jobs and mechanisms. Socket interface. Libraries like AMQP (here only simple things; patterns below in distributed systems?).
- Networking 4: Example socket programming. ECHO server, basic concepts. Connectionless, connection-oriented.
- Distributed Systems 1: Client/server. Web server. Hierarchies of servers. Server farms.
- Distributed Systems 2: Web frameworks. Programming for distributed systems. Tools. (Also things like: version control e.g., GIT; build server like Jenkins; remote management tools like Ansible or Puppet; Vagrant).
Exercises will be decided jointly with participants. Examples include, but are not limited to or comprising all of the following ones:
- CPU simulator: To understand instruction pointer, context, interrupts. (To be coordinated with PreMaster course Systems 1)
- A brief C introduction; write example programs in C.
- Signals as high-level interrupts. Write a signal handler in (typically, in C). Test it, e.g., SIGHUP or SIGTERM handler.
- Write multi-threaded programs in C. Write multi-process programs in C. Test performance on multi-core machines. Test things like thread/process creation time. Write programs for inter-process communication between processes, using shared memory.
- Use a scheduling simulator to play with scheduling algorithms.
- Write semaphore-based programs in different variants. Many examples. Try them out. Write alternative implementations of semaphores (e.g., different release scheduling in Passeeren).
- Write socket programs in C. Write AQMP programs in Python, using different patterns.
- Write a simple Web application, using a Web framework. database backend, etc. Full-fledged development and deployment cycle (DevOps): code in GIT, deploy by vagrant, install by ansible, triggered checkout.
This module will likely be a Reading class/inverted class room, depending on number of participants! Participants will be assigned textbook chapters to read and discuss them in class. Likely, one class meeting per week, with an additional homework discussion meeting.