Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Category Archives: computation

192: GIGO

Garbage In, Garbage Out.

To quote my numerical analysis professor John Strain, “If you have a really fancy method and give it garbage data, what you’ll get out is some really fancy garbage.”


191: Stability, Instability of Numerical Integration, Differentiation

Numerical integration methods such as use of the composite Simpson’s rule, composite trapezoidal rule, etc., are stable. That is, their round-off error as a result of being performed with machine arithmetic does not depend on the number of sub-intervals the integrating interval is split up into.

By contrast, numerical differentiation methods such as the 2-point, 3-point, and 5-point formulas are unstable, because these formulas involve division by the width of the step-size h used. So at a certain point as h \rightarrow 0, round-off error overtakes the increased accuracy of a small step-size and the approximations actually start to get worse.

188: Lagrange Interpolation

Given a real function f, a set of n+1 points x_0, \dots, x_n, and the values f(x_0), \dots, f(x_n) of f at those points, the Lagrange polynomial uses this information to give an n-th degree polynomial P which approximates f. The formula for P is

P = L_0 f(x_0) + \cdots + L_n f(x_n),


L_k = (\prod_{i \neq k} (x - x_i))/(\prod_{j \neq k} (x_k - x_j)).

Example: where n = 1 and we are given x_0, x_1, f(x_0), f(x_1), the Lagrange polynomial approximating f is

P = \frac{x - x_1}{x_0 - x_1} f(x_0) + \frac{x - x_0}{x_1 - x_0} f(x_1).

Examination of the polynomial should make it clear that it is, in a way, the simplest polynomial where P(x_k) = f(x_k) at each x_k.

168: Memory Leaks

In computing, a memory leak occurs when a program fails to release memory which is no longer required. For instance, a C program where the programmer dynamically allocates memory for a task but forgets to de-allocate it.

In certain circumstances, memory leakage may not cause big problems or might even be asymptomatic, like in programs with a little memory leakage which never actually run for long enough periods of time that memory usage becomes a problem. However, in worse cases memory leakage can lead to the complete failure of a program.

A couple types of programs at high risk for memory leakage are those in embedded systems (which can run continuously for years at a time, giving even small leaks the potential for being problematic) and those where memory is allocated extremely frequently for one-time tasks (such as rendering in a video or game).

While many languages like Java have built-in garbage collection which automatically cleans up unused or unaccessible memory, other languages like C and C++ require the programmer to be on top of making sure these leaks don’t happen in the first place. However, there are memory management libraries and memory debugging tools written to help with these languages. It should also be noted that automatic garbage collection comes with a performance overhead, so whether it’s desirable varies depending on the situation.

164: Instruction Pipelining

Instruction pipelining is a technique for increasing the throughput of a computer processor by executing instructions in parallel rather than sequentially.

Suppose you have several tasks to perform which each consist of stages s_1, \dots, s_n and each of these stages uses different resources than the others. One approach to completing a series of such tasks would be to complete one entirely before moving on to the next one, but since each stage of a task uses different resources, this approach leaves most resources sitting idle for unnecessary periods of time. To take advantage of this idleness, you can instead wait until stage 1 of task 1 is done, move it on to stage 2, and then while that is going just start task 2 on stage 1 using the stage 1 resources which are now available, continuing indefinitely in this manner.

A picture makes this idea clearer:


One sees that ideally, pipelining would increase the throughput of a processor by a factor of n, where n is the number of stages to an instruction. However, actually implementing pipelining is much more complicated than this abstraction, and the complications involved actually increase the latency of each individual instruction. Despite this increase in latency, if well-implemented pipelining still increases throughput by a significant factor. In fact, being clever about pipelining is usually the single most important factor in determining the CPI (cycles per instruction) of a processor.

163: Iron Law of Performance

In the study of computation, the Iron Law of Performance refers to the equation

\frac{\text{time}}{\text{program}} = \frac{\text{time}}{\text{cycle}} \cdot \frac{\text{cycles}}{\text{instruction}} \cdot \frac{\text{instructions}}{\text{program}},

which is just a way of roughly compartmentalizing the factors involved in determining how long it takes a program to execute.

While the first 2 terms depend on the instruction set architecture (ISA), microarchitecture, and base hardware technology involved, the 3rd depends mostly on things like the source code, the language the source code is written in, and the way the code is compiled.

146: Multiplexers

In circuit design, a multiplexer is a way of taking multiple inputs X_i and selecting which of those inputs to give as output based on the value of additional inputs S_j, called the select lines.

The simplest example which illustrates the idea is a multiplexer which selects between 2 binary inputs A and B based on the value of an additional binary input S. We could arbitrarily choose to give the value of A as the output if S = 0 and that of B as the output if S = 1.

The simplest boolean expression for the output Z which satisfies this requirement is

Z = A \cdot \bar{S} + B \cdot S.

It’s easy to see upon inspection that Z = A if S = 0 and Z = B otherwise, as required. (It should be noted, however, that building the multiplexer circuit as such, with just 2 AND gates, 1 OR gate, and 1 NOT gate would make the circuit susceptible to race conditions due to the physical realities of transistors.)

More generally, to make a multiplexer which selects output from n different inputs X_1, \dots, X_n, one needs to supply \lceil \log _2 n \rceil selector lines. The boolean expressions describing these multiplexers will get more complicated, of course, but the general idea is the same.

115: Race Conditions

In hardware or software systems, a race condition is a point in the system’s behavior which is critically dependent on timing issues.

In a software system, the issue could arise from two processes or threads which modify the same resources running at the same time, resulting in a resource modification error. In other words, two processes can modify the same resource and they try to modify it at the same time: they are “racing” to access it. A typical fix for this type of race condition is simply locking the resource so that only one process can access it at a time.

112: Persistent Data Structures

A data structure is said to be persistent if whenever it is modified or updated, it preserves the ‘old’ version of itself. This results in a kind of immutability. A good example of this is the simple singly-linked list, which whenever added onto contains the old version of itself in the new version.

111: Terminating Abstract Rewriting Systems

A terminating abstract rewriting system is one in which, given any starting element or term, there is no infinite sequence of rewritings which can be done on that starting element. That is, any sequence of rewritings on an element will eventually end in a ‘final’ rewritten form. Terminating ARSs are a subset of normal ARSs.