CPN CPE Computer Engineering flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Amdahl's law

Speedup from improving a fraction f of execution by factor s is 1/((1−f)+f/s). The unimproved portion caps the achievable gain regardless of s.

Average memory access time (AMAT)

AMAT equals hit time plus miss rate times miss penalty. Reducing any of the three terms improves processor memory performance.

Cache tag, index, offset

The offset selects a byte within a block, the index selects the set, and the tag is compared to confirm a hit. Remaining high address bits form the tag.

Pipeline hazard types

Structural hazards arise from resource conflicts, data hazards from dependencies between instructions, and control hazards from branches. Forwarding and stalls mitigate them.

De Morgan's laws

The complement of a product equals the sum of the complements, and the complement of a sum equals the product of the complements. Used to convert gate networks.

Setup and hold time

Setup time requires data stable before the clock edge; hold time requires it stable after. Violating either makes flip-flop capture unreliable.

Mealy versus Moore machine

Mealy outputs depend on present state and input, so they can change within a cycle. Moore outputs depend only on state and are glitch-free at outputs.

Carry-lookahead adder

Computes generate and propagate signals to predict carries in parallel, reducing the O(n) ripple delay to roughly O(log n) gate depth.

Deadlock four conditions

Mutual exclusion, hold-and-wait, no preemption, and circular wait must all hold simultaneously. Preventing any single condition prevents deadlock.

Belady's anomaly

FIFO page replacement can produce more page faults when given more frames. LRU and optimal replacement are stack algorithms and never exhibit it.

Thrashing

A process spends most time paging rather than executing because allocated frames are below its working set. CPU utilization drops as paging rises.

Priority inversion

A high-priority task waits on a lock held by a low-priority task that is preempted by a medium task. Priority inheritance bounds the delay.

TCP three-way handshake

Client sends SYN, server replies SYN-ACK, client sends ACK. This synchronizes sequence numbers and establishes both directions before data flows.

TCP slow start

Congestion window starts small and roughly doubles each round trip until a threshold, then grows linearly in congestion avoidance.

CIDR subnet host count

A /n prefix leaves 2^(32−n) addresses; a standard subnet yields 2^(32−n) − 2 usable hosts after reserving network and broadcast addresses.

NAT translation

Rewrites private source addresses and ports to a public address on egress and maps replies back using a translation table.

Coupling and cohesion

Coupling measures dependence between modules; cohesion measures relatedness within one module. Good design minimizes coupling and maximizes cohesion.

Cyclomatic complexity

V(G) = E − N + 2P for a control-flow graph. It equals the number of independent paths and a lower bound on test cases.

Merge versus rebase

Merge creates a commit with two parents and preserves history. Rebase replays commits onto a new base and rewrites their hashes.

Quicksort worst case

Occurs with unbalanced partitions, such as a first-element pivot on sorted input, giving O(n²). Randomized or median pivots make it unlikely.

Dijkstra's algorithm

Computes single-source shortest paths on graphs with non-negative edge weights using a priority queue, in O((V+E) log V) with a binary heap.

Dynamic programming conditions

Requires optimal substructure and overlapping subproblems. Memoization caches top-down results; tabulation fills a table bottom-up.

Third normal form

A relation is in 3NF when it is in 2NF and no non-key attribute depends transitively on a candidate key through another non-key attribute.

ACID properties

Atomicity all-or-nothing, consistency preserves constraints, isolation hides concurrent effects, durability survives crashes. Together they define reliable transaction behavior.

Covering index

An index containing all columns a query needs, so the database answers from the index without reading the table rows.

HMAC versus digital signature

HMAC authenticates with a shared secret and proves origin to key holders. A digital signature uses a private key and also gives non-repudiation.

Password salt

A unique random value stored with each password hash. It prevents precomputed rainbow tables and identical passwords hashing identically.

ECB mode weakness

Encrypts identical plaintext blocks to identical ciphertext blocks, leaking structural patterns. CBC, CTR, or GCM should be used instead.

Rate-monotonic scheduling

Fixed-priority preemptive policy assigning higher priority to shorter periods. Optimal among fixed-priority schemes; utilization bound approaches 0.693.

Earliest deadline first

Dynamic-priority preemptive scheduler that always runs the task with the nearest deadline. Optimal on one processor, reaching full utilization.

Watchdog timer

Hardware counter that resets the processor if software fails to service it in time. It recovers systems from hangs and runaway code.

Conflict of interest

A personal or financial interest that could improperly influence professional judgment. It must be disclosed and avoided or managed.