CSCE-312

Course Overview

• Course theme
• Five realities
• How the course fits into the CS/ECE curriculum
• Academic integrity

Course Theme

Abstraction Is Good But Don’t Forget Reality

• Most CS and CE courses emphasize abstraction
  • Abstract data types
  • Asymptotic analysis
• These abstractions have limits
  • Especially in the presence of bugs
  • Need to understand details of underlying implementations
• Useful outcomes from taking 312
  • Become more effective programmers
    • Able to find and eliminate bugs efficiently
    • Able to understand and tune for program performance
  • Prepare for later “systems” classes in CS & ECE
    • Compilers, Operating Systems, Networks, Computer Architecture, Embedded Systems, Storage Systems, etc.

Great Reality 1

Ints are not Integers, Floats are not Reals

• Example 1: Is x^2 ≥ 0?
  • Float’s: Yes!
  • Int's:
    • 40000 * 40000 ➙ 1600000000
    • 50000 * 50000 ➙ ??
• Example 2: Is (x + y) + z = x + (y + z)?
  • Unsigned & Signed Int’s: Yes!
  • Float’s:
    • (1e20 + -1e20) + 3.14 --> 3.14
    • 1e20 + (-1e20 + 3.14) --> ??

Computer Arithmetic

• Does not generate random values
  • Arithmetic operations have important mathematical properties
• Cannot assume all “usual” mathematical properties
  • Due to finiteness of representations
  • Integer operations satisfy “ring” properties
    • Commutativity, associativity, distributivity
  • Floating point operations satisfy “ordering” properties
    • Monotonicity, values of signs
• Observation
  • Need to understand which abstractions apply in which contexts
  • Important issues for compiler writers and serious application programmers

Great Reality 2

You’ve Got to Know Assembly

• Chances are, you’ll never write programs in assembly
  • Compilers are much better & more patient than you are
• But: Understanding assembly is key to machine-level execution model
  • Behavior of programs in presence of bugs
    • High-level language models break down
  • Tuning program performance
    • Understand optimizations done / not done by the compiler
    • Understanding sources of program inefficiency
  • Implementing system software
    • Compiler has machine code as target
    • Operating systems must manage process state
  • Creating / fighting malware
    • x86 assembly is the language of choice!

Great Reality 3: Memory Matters

Random Access Memory Is an Unphysical Abstraction

• Memory is not unbounded
  • "We have different delays for our memories"
  • It must be allocated and managed
  • Many applications are memory dominated
• Memory referencing bugs especially pernicious
  • Effects are distant in both time and space
• Memory performance is not uniform
  • Cache and virtual memory effects can greatly affect program performance
  • Adapting program to characteristics of memory system can lead to major speed improvements

Memory Referencing Bug Example

typedef struct {
	int a[2];
	double d;
}   struct_t;

double fun(int i) {
	volatile struct_t s;
	s.d = 3.14;
	s.a[i] = 1073741824; /* Possibly out of bounds */
	return s.d;
}

fun(0) ➙ 3.14
fun(1) ➙ 3.14
fun(2) ➙ 3.1399998664856
fun(3) ➙ 2.00000061035156
fun(4) ➙ 3.14
fun(6) ➙ Segmentation fault

• This is an undefined behavior

  • It starts with value 2, since this value of i is out of bounds in the array

• Result is system specific

Explanation:

• You have change the first chunk of memory of the next structure
• As you go beyond the space allocated for the struct you won't get a segmentation fault, when you reach the point where you write memory that is not allocated, then you will get the segmentation fault, this happens on fun(6)
• Volatile means: I do not want my compiler to optimize reading and writing for me
  • It might have change the order of everything and you would see undefined behavior otherwise

Memory Referencing Errors

• C and C++ do not provide any memory protection
  • Out of bounds array references
  • Invalid pointer values
  • Abuses of malloc/free
• Can lead to nasty bugs
  • Whether or not bug has any effect depends on system and compiler
  • Action at a distance
    • Corrupted object logically unrelated to one being accessed
    • Effect of bug may be first observed long after it is generated
• How can I deal with this?
  • Program in Java, Ruby, Python, ML, …
  • Understand what possible interactions may occur
  • Use or develop tools to detect referencing errors (e.g. Valgrind)

Great Reality 4

There’s more to performance than asymptotic complexity

• Constant factors matter too!
• And even exact op count does not predict performance
  • Easily see 10:1 performance range depending on how code written
  • Must optimize at multiple levels: algorithm, data representations, procedures, and loops
• Must understand system to optimize performance
  • How programs compiled and executed
  • How to measure program performance and identify bottlenecks
  • How to improve performance without destroying code modularity and generality

Memory System Performance Example

• Hierarchical memory organization

• Performance depends on access patterns

  • Including how step through multi-dimensional array

• If you are accessing the row and go to the next row you will be fast

• If you want to access one column of each row you will be very slow

• Execution time will be different always

Why The Performance Differs

Great Reality 5

Computers do more than execute programs

• They need to get data in and out
  • I/O system critical to program reliability and performance
• They communicate with each other over networks
  • Many system-level issues arise in presence of network
    • Concurrent operations by autonomous processes
    • Coping with unreliable media
    • Cross platform compatibility
    • Complex performance issues

Course Perspective

• Most Systems Courses are Builder-Centric
  • Computer Architecture
    • Design pipelined processor in Verilog
  • Operating Systems
    • Implement sample portions of operating system
  • Compilers
    • Write compiler for simple language
  • Networking
    • Implement and simulate network protocols

Course Perspective (Cont.)

• Our Course is Programmer-Centric
  • Purpose is to show that by knowing more about the underlying system, one can be more effective as a programmer
  • Enable you to
    • Write programs that are more reliable and efficient
    • Incorporate features that require hooks into OS
      • E.g., concurrency, signal handlers
  • Cover material in this course that you won’t see elsewhere
  • Not just a course for dedicated hackers
    • We bring out the hidden hacker in everyone!

Textbook

• Randal E. Bryant and David R. O’Hallaron,
  • Computer Systems: A Programmer’s Perspective, Third Edition (CS:APP3e), Pearson, 2016
  • http://csapp.cs.cmu.edu
  • This book really matters for the course!
    • How to solve labs
    • Practice problems typical of exam problems

Course Components

• Lectures
  • Higher level concepts
• Recitations
  • Applied concepts, important tools and skills for labs, clarification of lectures, exam coverage
• Homeworks (Labs)
  • The heart of the course
  • 1-2 weeks each
  • Provide in-depth understanding of an aspect of systems
  • Programming and measurement
• Exams (midterm + final)
  • Test your understanding of concepts & mathematical principles

Getting Help

• Class Web page: http://faculty.cse.tamu.edu/djimenez/312

  • “Complete” schedule of lectures, exams, and assignments
  • Copies of lectures, assignments, exams, solutions
  • Clarifications to assignments

• Teaching Assistants

• Peer Teachers

• Office Hours

• Ask Questions in Class!

Rules of the Lecture Hall

• Laptops: permitted
• Electronic communications: forbidden
  • No email, instant messaging, cell phone calls, etc
• Presence in lectures, recitations: voluntary, recommended

LAB 1

What is a register?

• Other level of memories that are closer to the material of the cpu, those are called ram and caches
• The faster ones are registers
  • Small memories very close to your cpu that are very very fast but they are super expensive, you have to manage them very well

li t0, 5
addi t0, t0, 10
mv tq, to

mov