栈和队列

栈（stack）实现的是一种后进先出策略。

STACK-EMPTY(S)
	if S.top == 0
		return TRUE
	else return FALSE
	
 PUSH(S, x)
	S.top = S.top + 1
	S[S.top] = x

POP(S)
	if STACK-EMPTY(S)
		error "underflow"
	else S.top = S.top - 1
		return S[S.top +1]

• 待排序的项称为 记录（record），每个记录包含一个 关键字（key），即排序问题中要重排的值，记录的剩余部分由 卫星数据（statellite data）组成。
• 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则称排序算法是 原址的（in place）。插入排序可以在$\Theta(n^2)$时间内将n个数排好序，是一种非常快的原址排序算法；归并排序有更好的渐近运行时间$\Theta(n\lg n)$，但它使用的MERGE过程并不是原址的。

算法基础

插入排序

//INSERTION-SORT(A)
for j = 2 to A.length
	key = A[j]
	//Insert A[j] into the sorted sequence A[1..j-1]
	i = j - 1 
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i+1] = key

• 循环不变式：初始化、保持、终止

###分析算法

• 单处理器计算模型：随机访问机（random-access machine，RAM）：算数指令、数据移动指令、控制指令。
• 最坏情况、平均情况、增长量级

Introduction

multiprocessor

A computer system with at least two processors. This is in contrast to a uniprocessor , which has one.

job-level parallelism or process-level parallelism

Utilizing multiple processors by running independent programs simultaneously.

parallel processing program

A single program that runs on multiple processors simultaneously.

cluster

A set of compters connected over a local area network (LAN) that functions as a single large message-passing multiprocessor.

multicore microprocessor

A microprocessor containing multiple processors (“cores”) in a single integrated circuit.

Introduction

Dependability, Reliability, and Availability

Dependability is the quality of delivered service such that reliance can justifiably be placed on this service.

Reliability is a measure of the continuous service accomplishment(or, equivalently, of the time to failure) from a reference point.

mean time to failure(MTTF) is a reliability measure. annual failure rate(AFR) is the percentage of devices that would be expected to fail in a year for a given MTTF. Service interruption is measured as mean time to repair(MTTR). Mean time between failures(MTBF) is simply the sum of MTTF and MTTR.

Availability is a measure of service accomplishment with respect to the alternation between the two states of accomplishment and interruption.

Availability = MTTF / MTBF

3 ways to improve MTTF:

1. Fault avoidance: preventing fault occurrence by construction.
2. Fault tolerance: using redundancy to allow the service to comply with the service specification despite faults occurring, which applies primarily to hardware faults.
3. Fault forecasting: predicting the presence and creation of faults, which applies to hardware and software faults, allowing the component to be replaced before it fails.

Introduction

Principle of locality

• Temporal locality : If a data location is referenced then it will tend to be referenced again soon.
• spatial locality : If a data location is referenced, data locations with nearby addresses will tend to be referenced soon.

Memory hierarchy

A structrue that uses multiple levels of memories; as the distance from the processor increases, the size of the memories and the access time both increase.

The main memory is implemented from DRAM, levels closer to the processor use SRAM, the largest and slowest level is usually magnetic disk.

Introduction

A abstract view of the implementation of the MIPS subset showing the major functional units and the major connections between them:

The basic implementation of the MIPS subset, including the necessary multiplexors and control lines:

asserted

The signal is logically high or true.

deasserted

The signal is logically low or false.

Clocking methodology

The approach used to determine when data is valid and stable relative to the clock.

Edge-triggered clocking

A clocking scheme in which all state changes occur on a clock edge.

control signal

A signal used for multiplexor selection or for directing the operation of a functional unit; contrasts with a data signal , which contains information that is operated on by a funcional unit.

The state element is changed only when the write control signal is asserted and a clock edge occurs.