CS250 Midterm 1 Pain and Suffering

What is software?

Computation expressed in programming language plus any data and documentation that goes along with it

What must software be able to do?

- Must define an algorithm + data structures

- Must be understandable to both programmers and to hardware

What is an interpreter?

Something that directly executes instructions expressed in a programming language

What types of interpreters are there?

Harvard architecture and Von Neumann architecture

Harvard Architecture

A computer architecture with physically separate storage and signal pathways for instructions and data. These early machines had data storage entirely contained within the central processing unit, and provided no access to the instruction storage as data.

Von Neumann Architecture

A processor where data and instructions are stored in the same memory and accessed via buses. Design is more flexible and economical than Harvard Architecture

What is abstraction?

Abstraction is a process of hiding the implementation details and showing only functionality to the user. Abstraction lets you focus on what the object does instead of how it does it.

Transistors

small electrical devices that could receive and amplify radio signals. Nowadays they are used in computer microchips.

Moore's law

a predication made by Gordon Moore in 1965 that computing power will double every 1.5-2 years, it has remained more or less true ever since.

What drives computer performance?

Hardware

Name the types of computers today

- Personal computers- PCs! What this is being written on. Graphics display, keyboard, mouse.

- Servers- modern form of larger computers, usually accessed via network. Run large programs for multiple users, often simultaneously.

- Supercomputers- most expensive + highest performance, used for high-end science + engineering calculations.

- Embedded computers- computers inside other devices, think a microwave. Very low cost, but higher chance of failure.

What is the post-pc era?

The era we're in now, where computers are being replaced w/ small wireless devices (like phones) that connect to the internet, rely on batteries for power, and software is installed through apps

Software as as Service

Apps are located in the cloud

Software experiences are delivered through the Internet

multicore processor

Integrated circuit to which two or more processors have been attached for enhanced performance, reduced power consumption and more efficient simultaneous processing of multiple tasks.

Tebibyte

2^40 bytes. Terabyte is 10^12, gigabyte is 10^9, so on and so forth.

Seven great ideas in computer architecture

1. Use abstraction to simplify design

2. Make the common case fast

3. Performance via parallelism

4. Performance via pipelining

5. Performance via prediction

6. Hierarchy of memories

7. Dependability via redundancy

Hierarchy of Memories

The fastest, smallest, and most expensive memory per bit at the top of the hierarchy and the slowest, largest, and cheapest per bit at the bottom.

Parts of the hierarchy of memories

- CPU registers

- Cache memory (SRAMS)

- Main memory (DRAMS)

- Magnetic disk (storage disk)

- Optical disk

- Magnetic tape

Systems Software

Provides services commonly useful like operating system (OS), compilers, sits between user and hardware

What two types of software exist in every computer?

- Compiler

- Operating system

Compiler

A program that translates code in a high-level language (such as Java) to machine instructions (such as bytecode for the Java virtual machine).

Operating System

Software, the interface between computer hardware and the user. Must be able to:

- Handle basic I/O functions

- Allocate storage and memory

- Provide protection for sharing of the computer among multiple applications using it simultaneously

How is hardware spoken to?

Electric signals, easiest to interpret is just on and off. (1's and 0's)

Bit

A contraction of "Binary Digit". A bit is the single unit of information in a computer, typically represented as a 0 or 1.

Bit strings

Sequences of ordered binary digits, 0s and 1s. Used to represent instructions for the computer to follow

Machine Language

The language made up of binary-coded instructions that is used directly by the computer. What computer hardware executes/interprets.

Assembler

A program that translates an assembly-language program into machine code

Why high-level programming languages are important

Allows programmers to think more naturally and therefore more quickly write code. In addition, they are independent of the computer it was developed on, so any assembler + compiler can translate the language into machine code

Process to compile a C program

- Source code, aka .c stuff. C preprocessor takes the .c file and transforms it into preprocessed source code (.i file), removing comments + evaluating all includes + defines

- Compiler takes the .i and turns it into a .s file, which contains assembly language.

- Assembler takes .s file and turns it into a .o file-step does not involve translation from one language to another. Assembly code has a one-to-one and onto functional relationship with the machine code of the computer.

- .o file is fed into linker which links up the file w/ libraries provided by include statements, generating the executable (binary object code!)

Two key components of hardware

Input and output devices, how to receive and display data respectively.

Five classic components of a computer are?

- Input: Receives data

- Output: displays data stored in memory

- Memory: Stores data

- Datapath: Operates on data received from input, performs arithmetic operations

- Control: Sends signals to determine operations of datapath, memory, and I/O according to instructions of the program

- last two are sometimes combined into the processor.

Graphics display

Monitor display that divides the screen into a matrix of small dots called pixels

liquid crystal display (LCD)

A flat-panel monitor that creates an image when liquid crystals become electronically charged. Essentially lots of rod-shaped molecules in a liquid form that bends in order to let light pass through.

How touch screen is implemented

Mainly implemented through electrostatic fields. Since people are electrical conductors, if an insulator like glass is covered with a transparent conductor, touching distorts the electrostatic field of the screen, which results in a change in capacitance. This technology can allow multiple touches simultaneously

integrated circuit

A group of tiny transistors and electric wires built on a silicon wafer, or chip.

Central Processing Unit (CPU)

Brain of the computer that performs instructions defined by software. Contains datapath and control, adds annd tests numbers, signals I/O devices to activate, etc.

Memory

Where programs are kept when they are running + contains data needed by running programs. Memory is a DRAM chip which provides random access to any location.

Cache memory

A type of memory used to temporarily store frequently used data or programs for quick access; similar to RAM but faster. Acts as a buffer for slower, larger memory.

Instruction Set Architecture (ISA)

Also called architecture. An abstract interface between the hardware and the lowest-level software that encompasses all the information necessary to write a machine language program that will run correctly, including instructions, registers, memory access, I/O, and so on.

Application Binary Interface (ABI)

The user portion of the instruction set plus the operating system interfaces used by application programmers. It defines a standard for binary portability across computers.

Volatile Memory

Storage (such as RAM chips) that is wiped clean when power is cut off from a device.

Nonvolatile Memory

Storage that retains data even when powered down (such as flash memory, hard disk, or DVD storage).

Flash Memory

Nonvolatile, chip-based storage, often used in mobile phones, cameras, and MP3 players. Sometimes called flash RAM, flash memory is slower than conventional RAM, but holds its charge even when the power goes out.

Main Memory

Closely connected to the processor, stored data are quickly and easily changed, holds the programs and data that the processor is actively working with. Also called primary memory.

Secondary Memory

Nonvolatile memory used to store programs and data between runs; typically consists of flash memory in PMDs and magnetic disks in servers.

Magnetic disk

Also called hard disk. A form of nonvolatile secondary memory composed of rotating platters coated with a magnetic recording material. Because they are rotating mechanical devices, access times are about 5 to 20 milliseconds and cost per gigabyte in 2012 was $0.05 to $0.10

Network

a group of two or more computer systems linked together

Advantages of networked computers

- Communication: Info is exchanged between computers at high speeds

- Resource sharing: Computers can share I/O devices

- Nonlocal access: users don't need to be new the computers they're using due to connecting computers over long distances

Local area network (LAN)

Connects a group of computers in close proximity, such as in an office building, school, or home

Wide Area Network (WAN)

Spans a large geographic area such as a state, province, or country

Affects of improved networking

A lot cheaper w/ higher capacity now, wireless stuff is now a thing, everything is a lot more efficient or whatever

Timeline of processors and memory

- 1951- vacuum tube, relative performance/unit cost: 1

- 1965- transistor, relative performance/unit cost: 35

- 1975- integrated circuit, 900

- 1995- Very large scale integrated circuit, 2400000

- 2020- ultra large scale integrated circuit, 500 billion ish

Transistor

on/off switch controlled by electricity

How transistors are made

- Transistors are made of silicon ingots which are sliced into wafers which go through a series of processing steps where patterns of chemicals are placed onto the wafers, creating the transistors, conductors, and insulators.

- Many independent components are placed onto a single wafer + then diced up into dies or chips so that if there's an imperfection, you only have to throw out a chip instead of a whole wafer.

What are we assessing in regards to "performance" of computers?

Speed and how fast a computer can get done certain functions

Response time

the time it takes to respond to user interactions such as a mouse click. People want this to decrease

Bandwidth/Throughput

The amount of data that can be transferred in a given time period. Datacenter managers want this to increase.

Hick's Law

The time it takes to make a decision increases as the number of alternatives increases

What do we want in regards to computer performance?

Increase performance, decrease execution time

How to measure time passed?

- Wall clock time

- CPU execution time

- User CPU time

- System CPU time

Wall clock time

The most straightforward definition of time is called wall clock time, response time, or elapsed time. These terms mean the total time to complete a task, including disk accesses, memory accesses, input/output (I/O) activities, operating system overhead—everything.

CPU execution time (CPU time)

The actual time the CPU spends computing for a specific task. CPU clock cycles * clock cycle time or CPU clock cycles/clock rate

User CPU Time (CPU Performance)

The CPU time spent in a program itself.

System CPU time

The CPU time spent in the operating system performing tasks on behalf of the program.

System performance

elapsed time on an unloaded system

clock cycles

Instruction Count x Cycles per Instruction, determines when events take place in the hardware

Clock period

The length of each clock cycle.

clock rate

The inverse of the clock period.

What tradeoff do designers face irt clock cycles?

Trade-off between the number of clock cycles needed for a program and the length of each cycle. Computer also has to deal w/ time it takes to execute instructions to run the program + how many instructions must be executed.

Clock cycles per instruction (CPI)

Average number of clock cycles per instruction for a program or program fragment.

What must we use to measure computer performance?

CPI, clock rate, and instruction count

What impacts program performance?

The algorithm, programming language, compiler, and ISA

Why does the algorithm affect program performance?

- Effects Instruction count, possibly CPI

- Determines # of source program instructions executed + # of processor instructions executed. May also affect CPI

Why does the programming language affect program performance?

- Affects instruction count + CPI

- Affects instruction count since statements must be translated to processor instructions + lang affects CPI since higher abstraction means more indirect calls, increasing instructions

Why does the compiler affect program performance?

- Instruction count, CPI

- Compiler determines translation of source language instructions to computer instructions, so a more efficient compiler will change instruction count + avg cycles per instruction.

Why does the ISA affect program performance?

- Affects instruction count, clock rate, CPI

- Affects instructions needed for a function, cost of cycles of each instruction, + overall clock rate of processor

Power wall

Period where lowering voltage was impossible because it made transistors too "leaky". This was circumvented by multiprocessors.

Common fallacies and pitfalls with computer hardware

- Improving one aspect of the computer doesn't necessarily mean that overall performance will increase by that exact same amount.

- Amdahl's Law

- Computers at low utilization can also use massive amounts of power

- Designing for performance and energy are linked to each other

- Must use all three factors-CPI, clock rate, and instruction count to measure performance.

Amdahl's Law

A rule stating that the performance enhancement possible with a given improvement is limited by the amount that the improved feature is used. It is a quantitative version of the law of diminishing returns. A system's speed is determined by its slowest component.

Why is designing for performance and energy linked together?

Energy is power over time, so less time spent in a program also means less energy spent. While the program is running, energy is being consumed.

million instructions per second (MIPS)

A measurement of program execution speed based on the number of millions of instructions. MIPS is computed as the instruction count divided by the product of the execution time and 10^6. It can be unreliable and vary between programs on a computer.

Ways to represent binary strings

Unsigned, signed, two's complement. Know all of this shit.

Two's Complement

A method in computing of being able to store negative numbers as string of pure binary digits. It works by turning the MSB into a sign bit, where 0 represents a positive number and 1 represents a negative.

Why do computers use unsigned and two's complement representation?

Because hardware for adding and subtracting them both are on the same circuit, saving money.

how to cast smaller bit integers to larger bit integers.

For unsigned, you just add more leading zeros. For 2's complement, you just copy the MSB and then add leading zeros in between, aka sign extension

How does overflow occur?

When the operation overwrites the most significant bit. 2^31 - 1 is the upper limit and 2^31 is the lower limit.

ASCII (American Standard Code for Information Interchange)

a code for representing English characters as numbers, with each letter assigned a number from 0 to 127. Since most programming languages have an origin that's old as shit, they use ASCII

Unicode

A character code that enables most of the languages of the world to be symbolized with a special character identification.

Big Endian

A CPU or memory architecture in which the most significant byte is stored at the lowest memory address.

Little Endian

Mirror of Big Endian, least significant byte first

Big Endian vs Little Endian

Big Endian Machine that stores the MSB Left to right

Little Endian machine stores LSB right to left.

Considerations for ISA

- Ability to execute every possible program (turing completeness) req little of ISA

- Tradeoffs among programming convenience (few lines of code for lots of computation), processor cost, and engineering considerations (circuits + processors generate heat but we want program to go fast)

Purpose of ISA

- Exists to control general purpose processor unit

- Bit string paired w/ machine rep must configure the circuit to execute a specific ISA instruction

ISA representation

Represented by bit strings

Opcode

- Selects ALU (algorithmic logic unit, performs operations on bit strings) to use

- Required, processor must be told what to do

- Encoding is designers choice, but decoding also takes time + money

- The field that denotes the operation and format of an instruction.

- The field may or may not have a valid meaning.

Operands

- Provide input to ALU

- Technically optional, opcode specifies how many is needed

- Encoding:

- Pointer to location storing operand value bit string

- Special: value rep bit string

Result field of ISA

- Must be a pointer to storage locations

- Optional (amount specified by opcode)

- Encoding:

- Pointer to the location to use to store result val bit string

- Not rare to see a 0-bit pter to the location for the result value

Two ways to design instruction size

Variable and fixed length

Variable Instruction Length pros and cons

Pros:

- Has unlimited capability of ISA, just add bytes

- Can select short encodings for commonly occurring instructions to reduce program size

Cons:

- Hard to prevent marketing from adding to ISA

- Instruction decryption = complex

- Variable anything = slower

- Compiler writers care some abt ISA capability, but few programmers actually code in machine lang

- TLDR, ppl don't really care that much about ISA capability

Fixed length instructions pros and cons

Pros:

- Easy to fetch fixed sized object from memory

- Few reps mean small chip area + energy use for decoding machine language

- ISA criteria is largely technical since bytes can't be added

- Compiler writers like smaller ISA since it decreases time + improves quality of translating high lvl to machine lang

Cons:

- Instructions can waste space by not using all bits of the space

- No marketing messages abt "expanded ISA"