Processes, text processing, memory and networking from the command line
A Jacobi solver for the Laplace problem on an interior grid of \(N=16\) points per side needs 515 sweeps to bring the largest change per sweep below \(10^{-6}\) and writes a log of 12 lines. The same solver at \(N=1000\) holds two grids of 15.3 MiB. In a separate run on this machine it stopped after 191,001 sweeps, 10.6 minutes at 3.3 ms per sweep, with a maximum error of 0.17 (the mode expansion of this chapter gives that error exactly), because its stopping rule bounds the change per sweep and not the error. A run that brings the error itself below \(10^{-6}\) needs about 2.6 million sweeps by the estimate derived in this chapter, which is 2.4 hours at the same speed. A person who starts such a run from a terminal on a shared login node must answer four questions with commands. Is the process alive, and in which state? How fast does the residual fall, and when will the run end? How much memory does the process hold? How do the log and the result reach another machine? The two lectures give the commands (ps, kill, grep, awk, sort, free, ping, ssh, scp and others) and illustrate the process and text commands on small files. This chapter defines the objects that the commands act on, runs the commands on the solver's own log, and tests the lectures' statements against the specifications and against runs on one machine. Among the tests: the residual ratio read from the log agrees with \(\cos(\pi/(N+1))\) to \(2\times10^{-7}\) in relative terms, and the mode expansion of the iteration reproduces the logged residuals in every printed digit, for \(N=16\) and for a separate 10-minute run at \(N=1000\).
Grounded in two recordings of the NPTEL course High Performance Scientific Computing (Prof. Shivasubramanian Gopalakrishnan, IIT Bombay): W1L5, Mastering Linux Text Processing and File Management (its spoken content is process management followed by text processing), and W1L6, Linux Memory and Networking Commands. Lecture material: the definition of a process and its attributes; background and foreground processes, & and fg; the process states running, sleeping, stopped and zombie; ps, ps -e, ps -ef, top and kill with the signals SIGTERM, SIGKILL, SIGSTOP and SIGCONT; multitasking, multiprocessing and multithreading; grep with -n and -r; awk for columns, conditions, arithmetic and patterns; sort and uniq; the pipe; wc, head, tail; the names diff, paste, tr and sed; the memory concepts virtual memory, swap space and paging with free, vmstat, df, swapon and meminfo; the loopback and physical network interfaces with ping, ip, ssh, wget and scp. Research extensions: POSIX.1-2017 (regular expressions, the shell pipeline and asynchronous list, grep, awk, sort, uniq); the GNU manuals for grep, gawk and coreutils; the Linux man-pages and the kernel documentation of /proc (process states, signals, pipes, wait, memory fields); Owens, Reppy and Turon (2009) for regular-expression derivatives; Cox (2007) for automata against backtracking, with Thompson (1968) known only through Cox; RFC 1122, RFC 792 and RFC 4251; the OpenSSH 9.0 release notes; Demmel's 1996 notes for the Jacobi spectral radius. Original teaching constructions: the formal model of streams, filters and pipelines; the derivative matcher and its comparison with grep; the awk estimator of the contraction factor and its derivation from the eigenmodes of the iteration; all programs, measurements and the six exercises.
The objects of the chapter and the running case
The chapter studies what a person can learn about a running numerical program from the command line. Seven kinds of object occur. A byte stream is a finite sequence of bytes read or written in order. A line is a sequence of zero or more bytes other than the newline byte, followed by one newline byte (POSIX.1-2017, Base Definitions §3.206). A text file is a stream that is a concatenation of lines. A filter is a program that reads one stream (standard input) and writes one stream (standard output); it also has an exit status and may write a second stream (standard error), which this section sets aside. A pipeline of filters \(f_1,\dots,f_k\) is the program that feeds the standard output of \(f_i\) to the standard input of \(f_{i+1}\) for \(i=1,\dots,k-1\). Viewed as a map on streams, its action is the composition \(f_k\circ\cdots\circ f_1\). A process is an executing instance of a program. It has a process identifier (PID), the identifier of its parent (PPID), the identifier of its user (UID) and a state. A signal is a numbered notification that the kernel or another process delivers to a process. The model of this section has one limit that later sections lift: the composition describes which bytes flow, and says nothing about timing, exit statuses, standard error or the concurrency of the stages.
The running case is the book's Jacobi iteration for the Laplace equation on the unit square. The grid has \((N+2)\times(N+2)\) points of type double, of which the \(N\times N\) interior points are updated. The value is 1 on the top edge and 0 on the other three edges, and the interior starts at 0. One sweep replaces each interior value by the mean of its four neighbours, and the residual \(r_k\) after \(k\) sweeps is the largest absolute change of any interior value in sweep \(k\). The solver stops when \(r_k\lt\mathrm{tol}\) with \(\mathrm{tol}=10^{-6}\). The listing below is the serial kernel of the book with a driver that writes a progress line at a fixed interval of sweeps. Its inputs are \(N\) and that interval, the second argument. Its outputs are the log on standard output and one diagnostic line on standard error. It has no other effect. The run in the listing sends the two streams to two files and prints both, so that the two streams stay visible as two streams.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IDX(i, j) ((i) * (N + 2) + (j))
/* One Jacobi sweep: write the 5-point average into the interior of unew,
return max |unew - u| over the interior. */
static double jacobi_step(int N, const double *u, double *unew)
{
double change = 0.0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
unew[IDX(i, j)] = 0.25 * (u[IDX(i - 1, j)] + u[IDX(i + 1, j)] +
u[IDX(i, j - 1)] + u[IDX(i, j + 1)]);
double d = unew[IDX(i, j)] - u[IDX(i, j)];
if (d < 0.0) d = -d;
if (d > change) change = d;
}
return change;
}
int main(int argc, char **argv)
{
int N = argc > 1 ? atoi(argv[1]) : 16;
int every = argc > 2 ? atoi(argv[2]) : 50;
double tol = 1.0e-6;
int max_iter = 20000;
size_t cells = (size_t)(N + 2) * (N + 2);
double *u = calloc(cells, sizeof *u), *unew = calloc(cells, sizeof *unew);
if (!u || !unew) return 1;
for (int j = 0; j < N + 2; j++) u[IDX(0, j)] = unew[IDX(0, j)] = 1.0; /* top edge */
fprintf(stderr, "jacobi_log: two grids of %zu doubles, %zu bytes\n", cells, 2 * cells * sizeof(double));
printf("# jacobi N=%d tol=%.1e max_iter=%d\n", N, tol, max_iter);
int k = 0;
double r = 1.0;
while (k < max_iter && r >= tol) {
r = jacobi_step(N, u, unew);
double *t = u; u = unew; unew = t;
k++;
if (k % every == 0) printf("iter %5d residual %.6e\n", k, r);
}
printf("# %s iter=%d residual=%.6e\n", r < tol ? "converged" : "stopped", k, r);
return 0;
}
--- solver.err
jacobi_log: two grids of 324 doubles, 5184 bytes
--- solver.log
# jacobi N=16 tol=1.0e-06 max_iter=20000
iter 50 residual 3.960505e-03
iter 100 residual 1.296030e-03
iter 150 residual 5.303838e-04
iter 200 residual 2.235469e-04
iter 250 residual 9.458274e-05
iter 300 residual 4.006077e-05
iter 350 residual 1.697280e-05
iter 400 residual 7.191545e-06
iter 450 residual 3.047196e-06
iter 500 residual 1.291163e-06
# converged iter=515 residual=9.979422e-07The log has a header line that records \(N\), the tolerance and the iteration limit; ten progress lines, one per 50 sweeps; and a final line that records that the run converged after 515 sweeps with residual \(9.979422\times10^{-7}\). The diagnostic line on standard error reports the memory of the two grids: \(324=18^2\) values per grid and \(5184=2\cdot324\cdot8\) bytes. Every later section works on this log or on the process that wrote it.
All measurements in the chapter come from one machine: an Intel Core i5-12450H laptop under Windows 11, a hybrid processor with 4 performance cores (two hardware threads each) and 4 efficiency cores (one thread each), that is 8 cores and 12 logical processors (Intel ARK). The programs run in a WSL 2 Ubuntu 24.04 guest, which presents the processor as 6 cores of 2 threads; that view is synthetic. The guest sees 15 GB of memory, and the programs were built with gcc 13.3. The lectures ran on a different system: the prompts in the slides read root@localhost and the top screen reports 3,861,052 KiB of memory. The tool versions below matter in two places, the definition of used in free and the behaviour of scp. The listing prints them as of 26 October 2026.
echo "kernel: $(uname -sr)"
echo "gawk: $(awk --version | head -n 1)"
echo "grep: $(grep --version | head -n 1)"
echo "sed: $(sed --version | head -n 1)"
echo "sort: $(sort --version | head -n 1)"
echo "ps: $(ps --version 2> /dev/null)"
echo "ssh: $(ssh -V 2>&1)"
echo "locales: $(locale -a | tr '\n' ' ')"
echo "page size: $(getconf PAGESIZE) bytes"
free -m | awk 'NR == 2 || NR == 3 {print $1, $2}'
if command -v meminfo > /dev/null; then echo "meminfo: a command"; else echo "meminfo: not a command; the fields are in /proc/meminfo"; fi
kernel: Linux 6.6.87.2-microsoft-standard-WSL2
gawk: GNU Awk 5.2.1, API 3.2, PMA Avon 8-g1, (GNU MPFR 4.2.1, GNU MP 6.3.0)
grep: grep (GNU grep) 3.11
sed: sed (GNU sed) 4.9
sort: sort (GNU coreutils) 9.4
ps: ps from procps-ng 4.0.4
ssh: OpenSSH_9.6p1 Ubuntu-3ubuntu13.19, OpenSSL 3.0.13 30 Jan 2024
locales: C C.utf8 POSIX
page size: 4096 bytes
Mem: 15829
Swap: 4096
meminfo: not a command; the fields are in /proc/meminfoPrograms whose output cannot vary are checked byte for byte. Four listings report timings, memory readings or version strings that change from run to run or from machine to machine; they are checked only by their return code, and the output printed under them is one sample run on this machine. The prose says so at each of the timing and memory listings and gives the range that repeated runs produced.
Processes, states and signals W1L5 0:06
The lecture defines a process as an executing instance of a program and lists its attributes: the PID, the PPID, the UID and the state (slide at W1L5 0:40). Process management, in the lecture's words, consists of creation, monitoring and control. This chapter treats monitoring and control. Chapter 2 treats creation (fork, exec, wait) and the kernel's scheduler, and chapter 5 uses exit statuses and $! inside shell scripts; signals and job control are treated only here.
Background and foreground
The lecture distinguishes two kinds of process. A foreground process occupies the terminal until it ends. A background process lets the terminal accept further commands. The lecture starts a background process by ending a command with &, as in sleep 100 &, and the shell answers with a job number and a PID ([1] 19883 on the slide). It brings the job back with fg %1. POSIX defines the mechanism. A command terminated by & runs as an asynchronous list: the shell does not wait for it, and the PID of its last command becomes available as $! (POSIX.1-2017, Shell Command Language §2.9.3). If job control is disabled, as in a script, the standard input of the asynchronous command is /dev/null; if job control is enabled, as in an interactive shell, the standard input remains the terminal. A background process that then reads the terminal receives SIGTTIN, whose default action is to stop it (signal(7)). The lecture describes sleep as putting the CPU into an idle state; that needs one correction. sleep blocks the calling process until the time has passed. The process uses no processor time and is in the sleeping state, but the processor is idle only if no other process is runnable.
A background process still belongs to the terminal's session. When the terminal closes, the kernel sends SIGHUP to the controlling process of the terminal, the shell (POSIX.1-2017, General Terminal Interface §11.1.10). An interactive Bash then resends SIGHUP to all its jobs, running or stopped (Bash manual, "Signals"), and the default action of SIGHUP is to terminate. nohup runs a command with hangup signals ignored, so that it continues after logout; if its standard output is a terminal, the output goes to nohup.out (GNU coreutils manual, nohup). The script below starts one ordinary background job and one job under nohup, sends SIGHUP to both, and reports what happens. It inspects only processes that it started, through the PIDs it captured in $!. Its outputs do not vary from run to run, so the check is exact. The lecture's fg is not part of the script, because fg needs an interactive terminal with job control, which the code lab does not provide.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
sleep 30 & # an ordinary background job
plain=$!
nohup sleep 30 > /dev/null 2>&1 & # the same job, started under nohup
immune=$!
sleep 0.2
echo "parent of the background job is this shell: $([ "$(ps -o ppid= -p $plain | tr -d ' ')" = "$$" ] && echo yes || echo no)"
echo "state of the two jobs: $(ps -o state= -p $plain) $(ps -o state= -p $immune)"
echo "standard input of the background job: $(readlink /proc/$plain/fd/0)"
kill -HUP $plain $immune # what the shell sends its jobs when the terminal closes
sleep 0.2
for name in plain immune; do
pid=${!name}
if kill -0 $pid 2> /dev/null; then echo "$name job after SIGHUP: alive"; else echo "$name job after SIGHUP: gone"; fi
done
wait $plain 2> /dev/null; echo "wait status of the plain job: $?"
kill $immune # SIGTERM, the default signal of kill
wait $immune 2> /dev/null; echo "wait status of the nohup job after SIGTERM: $?"
parent of the background job is this shell: yes
state of the two jobs: S S
standard input of the background job: /dev/null
plain job after SIGHUP: gone
immune job after SIGHUP: alive
wait status of the plain job: 129
wait status of the nohup job after SIGTERM: 143The five reports match the definitions. The parent of the background job is the shell that started it. Both jobs are in the sleeping state. The standard input of the job in a script is /dev/null. After SIGHUP the plain job is gone and the nohup job is alive. POSIX requires the exit status of a command that a signal terminated to be greater than 128 (POSIX.1-2017, Shell Command Language §2.8.2), and Bash reports 128 plus the signal number (Bash manual, "Exit Status"): 129 for SIGHUP and 143 for SIGTERM (\(128+15\)). The same rule explains the status 141 in a later section. For a run of hours on a cluster, nohup is the minimum, and chapter 30 treats the batch scheduler, which a shared login node requires for long jobs.
States
The lecture's slide at W1L5 6:40 lists four states with their ps letters: running (R), sleeping (S), stopped (T) and zombie (Z). The slide's definitions are correct: running means running or ready to run; sleeping means waiting for an event such as the completion of input or output; stopped means stopped by a signal such as SIGSTOP; a zombie has finished but still has an entry in the process table, awaiting cleanup by its parent. The spoken explanation differs from the slide in two places. The speaker says that a process goes to the waiting state because a higher-priority process arrives, and that a zombie is a finished process whose memory has not been cleaned. Both statements are tested below. The ps manual lists further codes: D, uninterruptible sleep, usually input or output; I, an idle kernel thread; and t, stopped by a debugger.
The program below creates one child per state and reads each state the way ps does, from the third field of /proc/PID/stat (proc_pid_stat(5)). A busy loop never blocks. A process in pause() sleeps until a signal arrives. SIGSTOP and SIGCONT stop and resume the sleeper. A child that exits at once and is not waited for becomes a zombie, and the program also tests whether its /proc/PID/status has a VmRSS line, the line that reports resident memory. The second part sends SIGTERM and SIGKILL, shows a SIGTERM that a process handles, and asks the kernel to install a handler for SIGKILL and for SIGSTOP. The third part pins two busy loops to logical processor 0 with sched_setaffinity and reads their states. Every output line is the same in every run, because each state is read 200 ms after the event that causes it and nothing else competes for the states. The check is exact.
#define _GNU_SOURCE
#include <errno.h>
#include <sched.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>
/* State letter of a process: the field after the command name in /proc/PID/stat. */
static char state_of(pid_t pid)
{
char path[64], buf[512];
snprintf(path, sizeof path, "/proc/%d/stat", (int)pid);
FILE *f = fopen(path, "r");
if (!f) return '?';
size_t n = fread(buf, 1, sizeof buf - 1, f);
fclose(f);
buf[n] = 0;
char *p = strrchr(buf, ')'); /* the command name may contain blanks */
return p ? p[2] : '?';
}
/* 1 if /proc/PID/status has a VmRSS line (a process that still owns user memory), else 0. */
static int has_vmrss(pid_t pid)
{
char path[64], line[256];
int found = 0;
snprintf(path, sizeof path, "/proc/%d/status", (int)pid);
FILE *f = fopen(path, "r");
if (!f) return -1;
while (fgets(line, sizeof line, f))
if (strncmp(line, "VmRSS:", 6) == 0) found = 1;
fclose(f);
return found;
}
static void settle(void) /* give the children 200 ms to reach their steady state */
{
struct timespec ts = {0, 200 * 1000 * 1000};
nanosleep(&ts, NULL);
}
static volatile sig_atomic_t got_term;
static void on_term(int sig) { (void)sig; got_term = 1; }
static pid_t spawn(int kind)
{
pid_t pid = fork();
if (pid) return pid;
if (kind == 0) { volatile unsigned long x = 0; for (;;) x++; } /* busy */
if (kind == 1) { for (;;) pause(); } /* sleeping */
if (kind == 2) _exit(0); /* ends at once */
signal(SIGTERM, on_term); /* kind 3: handles SIGTERM */
while (!got_term) pause();
_exit(7);
}
static void report(const char *what, pid_t pid)
{
int st;
waitpid(pid, &st, 0);
if (WIFSIGNALED(st))
printf("%-28s killed by signal %d (%s)\n", what, WTERMSIG(st), strsignal(WTERMSIG(st)));
else
printf("%-28s exited with status %d\n", what, WEXITSTATUS(st));
}
int main(void)
{
pid_t busy = spawn(0), sleeper = spawn(1);
settle();
printf("busy loop: %c waiting in pause(): %c\n", state_of(busy), state_of(sleeper));
kill(sleeper, SIGSTOP); settle();
printf("after SIGSTOP: %c\n", state_of(sleeper));
kill(sleeper, SIGCONT); settle();
printf("after SIGCONT: %c\n", state_of(sleeper));
pid_t zombie = spawn(2);
settle();
printf("child that exited, not waited for: %c, has a VmRSS line: %s\n",
state_of(zombie), has_vmrss(zombie) ? "yes" : "no");
report("zombie after waitpid:", zombie);
printf("/proc entry of the zombie after waitpid: %s\n", state_of(zombie) == '?' ? "gone" : "present");
kill(sleeper, SIGTERM); report("sleeper, SIGTERM:", sleeper);
kill(busy, SIGKILL); report("busy loop, SIGKILL:", busy);
pid_t handler = spawn(3);
settle();
kill(handler, SIGTERM); report("handler installed, SIGTERM:", handler);
struct sigaction sa;
memset(&sa, 0, sizeof sa);
sa.sa_handler = on_term;
errno = 0; sigaction(SIGKILL, &sa, NULL); printf("sigaction(SIGKILL): %s\n", strerror(errno));
errno = 0; sigaction(SIGSTOP, &sa, NULL); printf("sigaction(SIGSTOP): %s\n", strerror(errno));
pid_t a = spawn(0), b = spawn(0); /* two busy loops share one logical processor */
cpu_set_t one;
CPU_ZERO(&one); CPU_SET(0, &one);
sched_setaffinity(a, sizeof one, &one);
sched_setaffinity(b, sizeof one, &one);
settle(); settle();
printf("two busy loops on processor 0: %c %c\n", state_of(a), state_of(b));
kill(a, SIGKILL); kill(b, SIGKILL); waitpid(a, NULL, 0); waitpid(b, NULL, 0);
return 0;
}
busy loop: R waiting in pause(): S
after SIGSTOP: T
after SIGCONT: S
child that exited, not waited for: Z, has a VmRSS line: no
zombie after waitpid: exited with status 0
/proc entry of the zombie after waitpid: gone
sleeper, SIGTERM: killed by signal 15 (Terminated)
busy loop, SIGKILL: killed by signal 9 (Killed)
handler installed, SIGTERM: exited with status 7
sigaction(SIGKILL): Invalid argument
sigaction(SIGSTOP): Invalid argument
two busy loops on processor 0: R RThe first block confirms the slide: R for the busy loop, S for the process in pause(), T after SIGSTOP and S again after SIGCONT, since the process is still waiting. The zombie shows the correction of the spoken statement. The child has finished, its state is Z, and its status file has no VmRSS line: it owns no user memory. The kernel keeps its PID, its termination status and its resource-usage information so that the parent can collect them with wait, and the zombie occupies one slot of the process table until then; when the table is full, no process can be created (wait(2), NOTES). After waitpid the /proc entry is gone. A zombie therefore costs a process-table slot and its kernel bookkeeping, and no user memory, and the remedy is to make the parent wait, or to end the parent so that init waits (wait(2)).
The second block shows the lecture's signals. kill without an argument sends SIGTERM, number 15, whose default action is to terminate the process; kill(1) advises SIGTERM before SIGKILL because a process may install a handler for SIGTERM and clean up, as the fourth child does, which exits with status 7 instead of dying. SIGKILL, number 9, cannot be caught, blocked or ignored, and neither can SIGSTOP (signal(7)): sigaction fails with EINVAL, "Invalid argument", for both. The lecture's numbers 15, 9, and the pair of stop and continue agree with the manual for x86 and ARM: SIGSTOP is 19 and SIGCONT is 18, and the numbers differ on Alpha, SPARC, MIPS and PA-RISC (signal(7)), so scripts should use the names.
The third block tests the other spoken statement. Two busy loops share one logical processor, so at any instant at most one of them runs, and both are in state R. A preempted process stays runnable; it does not enter the sleeping state. The sleeping state means waiting for an event, and the scheduler's preference for another process does not create such an event. The same block makes precise the lecture's description of an HPC run in which each process, or each thread, works on one core. That layout is a choice, not a default: the affinity mask of a thread is the set of processors on which it may run, and the default allows all of them; sched_setaffinity narrows it (sched_setaffinity(2)). Without such a call, the kernel places and moves runnable threads among the allowed processors. Chapter 11 returns to the choice of binding for OpenMP threads, and chapter 8 treats concurrency.
Monitoring
The lecture's monitoring commands are ps, ps -e, ps -ef and top. By default ps selects the processes that have the same effective user ID as the caller and the same terminal; -e selects all processes, and -f adds columns including the parent PID and the command arguments (ps(1)). The slide's ps -e output begins with systemd as PID 1 and kthreadd as PID 2, with kernel threads below it. The lecture presents ps -e as listing all processes, including killed, stopped and zombie ones; that is right for stopped and zombie processes, which exist, and wrong for killed processes once their parent has waited for them, because they no longer exist.
The top screen on the slide at W1L5 11:26 can be checked against itself. The task line reads 207 total, 1 running, 206 sleeping, 0 stopped, 0 zombie, and \(1+206+0+0=207\). The processor line reads 1.7 us, 0.7 sy, 0.0 ni, 97.3 id, 0.3 wa, 0.0 hi, 0.0 si, 0.0 st, and the eight values add to 100.0. The memory line gives 3,861,052 KiB total, 1,373,776 free, 1,064,472 used and 1,422,804 buffers and cache, and \(1{,}373{,}776+1{,}064{,}472+1{,}422{,}804=3{,}861{,}052\). The first process, gnome-shell, has a resident size of 183,760 KiB, and \(183{,}760/3{,}861{,}052=4.76\,\%\), which the screen prints as 4.8 in the %MEM column. The top manual defines %MEM as the resident size as a share of physical memory, and %CPU as the task's share of the elapsed processor time since the last screen update; for a multi-threaded process that top shows as one task, the value can exceed 100 % (top(1)). The screen has no column for the graphics processor, and the top manual describes none. GPU utilization has its own tools, which chapter 17 introduces.
Multitasking, multiprocessing and multithreading W1L5 16:30
The lecture closes the process topic with three terms, presented as the operating-system support on which OpenMP and MPI programs rest. Multitasking is the execution of several processes over the same period: the kernel switches a processor from one runnable process to another (a context switch), so on \(p\) logical processors at most \(p\) processes run at any instant and the other runnable processes wait in state R. Multiprocessing, in the lecture's sense, is an application made of several processes, each with its own address space, which the kernel schedules and which exchange data through inter-process communication (pipes, signals, sockets, shared memory); an MPI program (chapter 14) has this structure. The word also has a hardware sense, a machine with several processors. Multithreading is one process that contains several threads: the threads share the address space and the open files of the process, and each has its own registers, stack and scheduling state; Linux schedules each thread as a separate task (clone(2), CLONE_THREAD). An OpenMP program (chapter 11) has this structure. The third block of states.c shows multitasking on one processor: two runnable processes share processor 0 and both are in state R.
grep and the language of a regular expression W1L5 21:56
The lecture introduces grep as the command that searches for a string or pattern in files or input streams. Its example file has four lines, two of which contain the word Ved; grep "Ved" file3 prints those two lines, grep -n prefixes each with its line number, and grep -r "Ved" * searches the files and directories below the current directory. The lecture calls the argument a string or pattern and does not say what patterns exist. This section defines them.
The language of an expression
Let \(\Sigma\) be a finite alphabet, here the set of characters. A regular expression is built by the grammar \(r,s::=\varnothing\mid\varepsilon\mid a\mid rs\mid r+s\mid r^{*}\) with \(a\in\Sigma\). Its language \(\mathcal L(r)\subseteq\Sigma^{*}\) is the set of strings given by \(\mathcal L(\varnothing)=\varnothing\), \(\mathcal L(\varepsilon)=\{\varepsilon\}\), \(\mathcal L(a)=\{a\}\), \(\mathcal L(rs)=\{uv: u\in \mathcal L(r),\,v\in \mathcal L(s)\}\), \(\mathcal L(r+s)=\mathcal L(r)\cup \mathcal L(s)\) and \(\mathcal L(r^{*})=\{\varepsilon\}\cup \mathcal L(rr^{*})\), an equation whose least solution is \(\mathcal L(r^{*})=\bigcup_{n\ge0}\mathcal L(r)^{n}\) with \(\mathcal L^{0}=\{\varepsilon\}\) and \(\mathcal L^{n+1}=\{uv:u\in \mathcal L,\,v\in \mathcal L^{n}\}\) (Owens, Reppy and Turon 2009, Definitions 2.1 and 2.2). The notation of grep -E abbreviates these operators: \(r|s\) is \(r+s\); \(r?\) is \(\varepsilon+r\); \(r^{+}\) is \(rr^{*}\); . is the sum of all characters; a bracket expression such as [ab] is the sum of its members; an interval such as a{2,3} is a finite sum of concatenations. POSIX writes the same constructs as the extended regular expression (ERE) grammar and, with other escapes, as the basic regular expression (BRE) grammar (POSIX.1-2017, Base Definitions §9.3 to §9.5). The anchors ^ and $ do not describe sets of strings but positions at the start and end of a line.
What grep does with a language is a search. A line \(\ell\) is selected if \(\ell=xyz\) for some strings \(x,y,z\) with \(y\in \mathcal L(r)\). With the option -x the line is selected only if \(\ell\in \mathcal L(r)\). The two statements are connected by \(\ell\) being selected by \(r\) exactly when \(\ell\in \mathcal L(\texttt{.*(}r\texttt{).*})\). For an expression whose match is wanted, not only the decision, POSIX adds a rule: the search starts at the beginning of the string and stops at the first sequence that matches, "first" meaning "begins earliest", and if several sequences begin there, the longest is matched (POSIX.1-2017, Base Definitions §9.1). The rule matters for grep -o and for sed, which print or replace the match; it does not change which lines grep selects.
A matcher that is the definition
The decision "is \(u\in \mathcal L(r)\)" can be computed from the definition by derivatives. The derivative of a language \(\mathcal L\) by a character \(a\) is \(\partial_a \mathcal L=\{w: aw\in \mathcal L\}\). Two functions on expressions compute it. The function \(\nu\) tests whether \(\varepsilon\in \mathcal L(r)\): \(\nu(\varepsilon)=\nu(r^{*})=\mathrm{true}\), \(\nu(\varnothing)=\nu(a)=\mathrm{false}\), \(\nu(rs)=\nu(r)\wedge\nu(s)\), \(\nu(r+s)=\nu(r)\vee\nu(s)\). The derivative of an expression is
\[ \partial_a(\varnothing)=\partial_a(\varepsilon)=\varnothing,\quad \partial_a(b)=\begin{cases}\varepsilon&b=a\\ \varnothing&b\ne a,\end{cases}\quad \partial_a(r+s)=\partial_a r+\partial_a s,\quad \partial_a(r^{*})=(\partial_a r)\,r^{*}, \tag{4.1} \] \[ \partial_a(rs)=\begin{cases}(\partial_a r)\,s+\partial_a s&\nu(r)\\ (\partial_a r)\,s&\text{otherwise,}\end{cases} \tag{4.2} \](Owens, Reppy and Turon 2009, §3.1, due to Brzozowski 1964; the paper of 1964 was not opened, and its bibliographic data were checked in Crossref). For a string \(u=a_1\cdots a_n\), \(u\in \mathcal L(r)\) exactly when \(\nu(\partial_{a_n}\cdots\partial_{a_1}r)\) holds (§3.2 of the same paper). Two facts carry the proof. The first is the definition: \(u\in \mathcal L(r)\iff\varepsilon\in\partial_u \mathcal L(r)\), where \(\partial_{a_1\cdots a_n}=\partial_{a_n}\circ\cdots\circ\partial_{a_1}\). The second is that the rules compute the derivative of the language, \(\mathcal L(\partial_a r)=\partial_a \mathcal L(r)\), by induction on \(r\). Only concatenation and star need care. If \(aw\in \mathcal L(r)\mathcal L(s)\), either the part from \(\mathcal L(r)\) is \(au'\) with \(u'v=w\) and \(v\in \mathcal L(s)\), so that \(w\in(\partial_a\mathcal L(r))\mathcal L(s)\), or the part from \(\mathcal L(r)\) is empty, which requires \(\varepsilon\in \mathcal L(r)\) and gives \(w\in\partial_a\mathcal L(s)\); this is (4.2). A string of \(\mathcal L(r)^{*}\) that begins with \(a\) has a first non-empty factor \(au'\in \mathcal L(r)\) followed by a string of \(\mathcal L(r)^{*}\), so \(\partial_a\mathcal L(r^{*})=(\partial_a\mathcal L(r))\,\mathcal L(r^{*})\), the last rule of (4.1). Since \(\nu(r)\) is true exactly when \(\varepsilon\in \mathcal L(r)\), the two facts give the matching rule. The listing implements (4.1) and (4.2) for the subset of ERE with characters, ., grouping, |, *, + and ?. It enumerates all 127 strings of length 0 to 6 over \(\{a,b\}\), and for seven expressions it compares the set accepted by the derivative matcher with the set of lines that grep -E -x selects. It also compares the lines that plain grep -E selects with the language of \(\texttt{.*(}r\texttt{).*}\), which tests the search identity of the previous subsection. The program is deterministic, so the check is exact. The check covers the strings of length at most 6 and the listed expressions; it is not a proof that grep implements the definition for every expression.
"""Check the formal definition of a regular expression against grep -E.
The matcher implements the definition directly: nullable(r) tests whether the empty
string is in L(r), and deriv(r, a) is the expression for { w : a w in L(r) }.
A string u is in L(r) exactly when the derivative of r by the characters of u is nullable.
"""
import itertools
import subprocess
# Abstract syntax: ('empty',) no string; ('eps',) the empty string; ('chr', c);
# ('any',) any one character of the alphabet; ('cat', r, s); ('alt', r, s); ('star', r).
ALPHABET = "ab"
def parse(p):
"""Parse the ERE subset a b . ( ) | * + ? into the syntax above."""
pos = 0
def peek():
return p[pos] if pos < len(p) else None
def alt():
nonlocal pos
r = cat()
while peek() == "|":
pos += 1
r = ("alt", r, cat())
return r
def cat():
r = ("eps",)
while peek() not in (None, "|", ")"):
r = rep() if r == ("eps",) else ("cat", r, rep())
return r
def rep():
nonlocal pos
if peek() == "(":
pos += 1
r = alt()
pos += 1 # the closing parenthesis
elif peek() == ".":
pos += 1
r = ("any",)
else:
r = ("chr", p[pos])
pos += 1
while peek() in ("*", "+", "?"):
op = p[pos]
pos += 1
r = ("star", r) if op == "*" else ("cat", r, ("star", r)) if op == "+" else ("alt", r, ("eps",))
return r
return alt()
def nullable(r):
k = r[0]
if k == "eps" or k == "star":
return True
if k in ("empty", "chr", "any"):
return False
if k == "cat":
return nullable(r[1]) and nullable(r[2])
return nullable(r[1]) or nullable(r[2]) # alt
def deriv(r, a):
k = r[0]
if k in ("empty", "eps"):
return ("empty",)
if k == "chr":
return ("eps",) if r[1] == a else ("empty",)
if k == "any":
return ("eps",)
if k == "alt":
return ("alt", deriv(r[1], a), deriv(r[2], a))
if k == "star":
return ("cat", deriv(r[1], a), r)
first = ("cat", deriv(r[1], a), r[2]) # cat
return ("alt", first, deriv(r[2], a)) if nullable(r[1]) else first
def matches(r, u):
for a in u:
r = deriv(r, a)
return nullable(r)
strings = [""] + ["".join(t) for n in range(1, 7) for t in itertools.product(ALPHABET, repeat=n)]
with open("strings.txt", "w") as f:
f.write("\n".join(strings) + "\n")
print(f"{len(strings)} strings over {{a,b}} of length 0 to 6")
print("pattern in L(r) grep -E -x same | lines grep -E selects same as L(.*(r).*)")
for pattern in ["a*b", "(a|b)*abb", "(ab)+|b?", "a.a", "((a|b)(a|b))*", "a*(ba*)*", "bab"]:
r = parse(pattern)
mine = {u for u in strings if matches(r, u)}
out = subprocess.run(["grep", "-E", "-x", pattern, "strings.txt"], capture_output=True, text=True).stdout
theirs = set(out.split("\n")[:-1])
search = parse(".*(" + pattern + ").*")
mine_search = {u for u in strings if matches(search, u)}
out = subprocess.run(["grep", "-E", pattern, "strings.txt"], capture_output=True, text=True).stdout
theirs_search = set(out.split("\n")[:-1])
print(f"{pattern:16s} {len(mine):7d} {len(theirs):11d} {'yes' if mine == theirs else 'NO':>4s} | "
f"{len(theirs_search):21d} {'yes' if mine_search == theirs_search else 'NO'}")
127 strings over {a,b} of length 0 to 6
pattern in L(r) grep -E -x same | lines grep -E selects same as L(.*(r).*)
a*b 6 6 yes | 120 yes
(a|b)*abb 15 15 yes | 48 yes
(ab)+|b? 5 5 yes | 127 yes
a.a 2 2 yes | 65 yes
((a|b)(a|b))* 85 85 yes | 127 yes
a*(ba*)* 127 127 yes | 127 yes
bab 1 1 yes | 43 yesThe derivative matcher and grep select the same strings in all seven rows, both for whole-line matching and for the search identity. The counts can be checked by hand: a*b accepts \(a^kb\) for \(k=0,\dots,5\), six strings; (a|b)*abb accepts the strings that end in abb, \(1+2+4+8=15\) of lengths 3 to 6; ((a|b)(a|b))* accepts the strings of even length, \(1+4+16+64=85\); and a.a accepts aaa and aba.
Cost: automata against backtracking
The derivative matcher of the listing is a teaching device and not how grep works. Cox (2007) describes two families of implementations. One simulates a nondeterministic finite automaton built from the expression, the construction that Thompson published in 1968, or builds a deterministic one; Cox lists GNU grep and GNU awk among the implementations that build deterministic automata. The simulation takes time \(O(|r|n)\) for an expression of length \(|r|\) and a text of length \(n\). The other family tries the alternatives one after another and backtracks on failure; Perl and the languages that copied it do this, and Cox's example is the expression \(a?^{n}a^{n}\) (\(n\) optional a followed by \(n\) required ones) against the string \(a^{n}\), on which backtracking takes time exponential in \(n\), while the automaton takes microseconds. The listing repeats the experiment with the backtracking matcher of Python's re module and with grep -E. It times one call of each per \(n\), checks that both report a match, and uses only the return codes for the check. The times printed under it are one sample run on this machine.
"""Time a backtracking matcher (Python re) and grep -E on the pattern a?^n a^n against a^n."""
import re
import subprocess
import time
print(" n python re (s) grep -E process (s) both match")
for n in (16, 20, 22, 24, 26):
pattern = "a?" * n + "a" * n
text = "a" * n
t0 = time.perf_counter()
py = re.fullmatch(pattern, text) is not None
t_py = time.perf_counter() - t0
t0 = time.perf_counter()
gr = subprocess.run(["grep", "-E", "-x", pattern], input=text + "\n", capture_output=True, text=True).returncode == 0
t_gr = time.perf_counter() - t0
print(f"{n:2d} {t_py:14.4f} {t_gr:21.4f} {py and gr}")
n python re (s) grep -E process (s) both match
16 0.0017 0.0018 True
20 0.0288 0.0019 True
22 0.1205 0.0020 True
24 0.5043 0.0015 True
26 2.2845 0.0024 TrueIn this sample the Python time grows by a factor of 4.2 to 4.5 for each increase of \(n\) by 2 (0.0288 s, 0.1205 s, 0.5043 s and 2.2845 s at \(n=20,22,24,26\)); in two other runs the factors were 3.9 to 4.3. A time proportional to \(2^{n}\) gives a factor of 4 per step of 2, so the growth is exponential with a base close to 2. The grep process time stays between 1.5 and 2.4 ms in this sample, which is mostly the cost of starting the program. At \(n=26\) the Python time was 2.3 s in this sample and 1.9 s and 1.8 s in the two other runs, which is at least 950 to 1300 times the matching time of grep, because the grep figure is mostly process start-up, for an input of 26 characters; the Python time roughly doubles for every increase of \(n\) by 1. Cox reports the same shape for Perl and states that Thompson's algorithm handles a 100-character input in under 200 microseconds. The lesson for a log parser is limited: a pattern without back-references is safe from this blow-up in grep -E, and the same pattern handed to a backtracking library may not be.
Where the notation leaves the regular languages
A back-reference such as \1 matches the text that an earlier group matched. GNU grep accepts it in both syntaxes (GNU grep manual, §3.5), and POSIX specifies it for BRE; the ERE grammar of POSIX has no back-reference. The pattern ^(.+)\1$ selects the strings of the form \(ww\), the squares. The set of squares is not a regular language, so no expression built from \(\varnothing,\varepsilon,a,rs,r+s,r^{*}\) describes it, and a matcher for back-references cannot be a finite automaton. Cox states that, with back-references, the best known implementations need exponential search in the worst case. The shell script of the next section shows the pattern at work. The other places where GNU grep departs from the model are these. In BRE the characters ?, +, {, |, ( and ) lose their special meaning (GNU grep manual, §3.6). POSIX BRE has the groups \( and \) and the intervals \{ and \}; the forms \+, \? and \| are GNU extensions, and POSIX.1-2017 §9.3 defines none of the three. A bracket range such as [a-z] is defined by the collation order of the locale; POSIX specifies it only for the POSIX locale (Base Definitions §9.3.5). The machine used here offers only the locales C, C.utf8 and POSIX, so the chapter does not test other collation orders. A script that parses a log should set LC_ALL=C so that the character classes and the sort order do not depend on the user's locale.
awk: records, fields and pattern–action pairs W1L5 25:31
The lecture describes awk as a tool for pattern scanning and text extraction and demonstrates four uses on a file of three lines, each with a name, an age and a letter (John 25 M, Alice 30 F, Bob 28 M): printing columns 1 and 3, printing the first column of the rows whose third column is M, printing the name and twice the age, and printing the lines that match /John/ or /M/. The lecture does not state the execution model that makes the four programs instances of one rule.
An awk program is a list of pattern–action pairs, written pattern { action } (GNU awk manual, chapter 1, "Getting Started with awk"). The program reads its input as a sequence of records, by default the lines. For each record it splits the text into fields, sets the variable $0 to the whole record, $1, $2, … to the fields, NF to their number and NR to the record number, and then runs the action of every pair whose pattern is true for the record. An omitted pattern is true for every record, and an omitted action prints $0. The patterns BEGIN and END run once, before the first record and after the last (GNU awk manual, §7.1.4). Variables that were never assigned have the value zero and the empty string at once. Arithmetic follows the floating-point semantics of the ISO C standard, so awk computes in double (POSIX.1-2017, awk, Expressions). By default a run of blanks separates fields, and leading and trailing blanks are ignored; the default value of FS is a single space, which is a special case, and any other single character, such as a comma, separates every pair of occurrences, so two commas in a row delimit an empty field (GNU awk manual, §4.5.1).
The script below reproduces the four lecture programs and checks the points above. It recreates the lecture's small files in a fresh directory; its other commands belong to the sections that follow and are printed in one output. The three-line file and its commands are the lecture's; the file with a woman named Mary, the field-splitting checks and the comparison of numeric strings are added. Everything in the script is deterministic, so the check is exact.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
printf 'John 25 M\nAlice 30 F\nBob 28 M\n' > file.txt
echo "== awk '{print \$1, \$3}'"; awk '{print $1, $3}' file.txt
echo "== awk '\$3 == \"M\" {print \$1}'"; awk '$3 == "M" {print $1}' file.txt
echo "== awk '{print \$1, \$2 * 2}'"; awk '{print $1, $2 * 2}' file.txt
echo "== awk '/M/ {print \$0}'"; awk '/M/ {print $0}' file.txt
printf 'John 25 M\nMary 30 F\nBob 28 M\n' > file_mary.txt
echo "== the same /M/ program on a file that has a woman named Mary"
awk '/M/ {print $0}' file_mary.txt
echo "== the anchored test on the same file"
awk '$3 == "M" {print $0}' file_mary.txt
echo "== field splitting: runs of blanks separate fields, one comma separates two"
printf 'a b\n' | awk '{print NF}'
printf 'a b\n' | awk -F' ' '{print NF}'
printf 'a,,b\n' | awk -F, '{print NF}'
printf 'Mango is Yello\nApple is red\nGreen Vegetables\n' > file2
echo "== sort file2"; sort file2
echo "== sort -r file2"; sort -r file2
printf 'Mango is Yello\nApple is red\nMango is Yello\nGreen Vegetables\n' > file2
echo "== sort file2 | uniq"; sort file2 | uniq
echo "== wc file2"; wc file2
echo "== wc -l, -w, -c"; wc -l file2; wc -w file2; wc -c file2
printf 'Mango is Yello\nApple is red\nOrange is Orange\nGreen Vegetables\nPitter is student\n' > file4
echo "== head -2 file4 and tail -2 file4"; head -n 2 file4; tail -n 2 file4
printf 'Hello Ved !\nHow are you ?\nVed is good student.\nHe is talented !\n' > file3
echo "== grep, grep -n"; grep "Ved" file3; grep -n "Ved" file3
mkdir Test; echo "Ved is child of Mr. Shyam" > Test/Child.txt
echo "== grep -r"; grep -r "Ved" * | sort
echo "== diff, paste, tr"
printf 'one\ntwo\nthree\n' > f1; printf 'one\n2\nthree\n' > f2
diff f1 f2
paste f1 f2 | tr '\t' ' '
echo "Hello" | tr 'a-z' 'A-Z'
echo "== a field that looks like a number compares as a number, a string compares as text"
echo "10 9" | awk '{print ($1 < $2), ($1 "" < $2 "")}'
== awk '{print $1, $3}'
John M
Alice F
Bob M
== awk '$3 == "M" {print $1}'
John
Bob
== awk '{print $1, $2 * 2}'
John 50
Alice 60
Bob 56
== awk '/M/ {print $0}'
John 25 M
Bob 28 M
== the same /M/ program on a file that has a woman named Mary
John 25 M
Mary 30 F
Bob 28 M
== the anchored test on the same file
John 25 M
Bob 28 M
== field splitting: runs of blanks separate fields, one comma separates two
2
2
3
== sort file2
Apple is red
Green Vegetables
Mango is Yello
== sort -r file2
Mango is Yello
Green Vegetables
Apple is red
== sort file2 | uniq
Apple is red
Green Vegetables
Mango is Yello
== wc file2
4 11 60 file2
== wc -l, -w, -c
4 file2
11 file2
60 file2
== head -2 file4 and tail -2 file4
Mango is Yello
Apple is red
Green Vegetables
Pitter is student
== grep, grep -n
Hello Ved !
Ved is good student.
1:Hello Ved !
3:Ved is good student.
== grep -r
Test/Child.txt:Ved is child of Mr. Shyam
file3:Hello Ved !
file3:Ved is good student.
== diff, paste, tr
2c2
< two
---
> 2
one one
two 2
three three
HELLO
== a field that looks like a number compares as a number, a string compares as text
0 1The first four blocks of the output are the lecture's four programs: the columns John M, Alice F, Bob M; the names John and Bob; the doubled ages 50, 60 and 56; and the two lines that contain M. The next two blocks show a difference that the lecture does not draw. The pattern /M/ is a regular expression and selects any line that contains an M anywhere, so Mary 30 F is selected although the third field is F. The pattern $3 == "M" compares one field and selects the right lines. The lecture's output is correct for its file, and the first program is wrong for any file that has an M elsewhere in a line. The field-splitting block shows that three blanks between a and b give two fields, with and without the explicit -F' ', and that a,,b split at commas gives three. The last block shows the rule for comparison. A field that looks like a number is compared as a number: 10 < 9 is false. The same two fields, joined to the empty string so that they become text, are compared as text: "10" < "9" is true, because the character 1 precedes 9.
One pass of awk over a log keeps a constant amount of state for a sum, a maximum or a ratio, which is why it suits the running case. Two programs in the following sections are examples. The first extracts the first and last residual and their count from the solver's log. The second computes the contraction factor of the iteration from the last two progress lines and compares it with the theoretical value.
Sorting, counting and the pipeline W1L5 30:29
sort and uniq
The lecture shows sort file2 arranging the lines Mango is Yello, Apple is red, Green Vegetables alphabetically, mentions numerical sorting, and shows -r for the reverse order. sort compares whole lines, or keys within them, by the collation order of the locale, and in the C locale by byte value (GNU coreutils manual, sort). Two options order numbers. -n reads an initial numeric string: optional blanks, an optional minus sign, digits with an optional decimal point (POSIX.1-2017, sort); GNU sort states that exponential notation is not recognized. -g converts a prefix to a floating-point number and does recognize exponents. A residual log is the case in which the two differ, since every residual has an exponent. The lecture's uniq slide says "filters out duplicate lines from sorted input". uniq discards all but the first of adjacent repeated lines; the input need not be sorted, but non-adjacent repeats stay, and sort -u is the one-command alternative (GNU coreutils manual, uniq). The lecture's example sorts the file with Mango is Yello twice and passes the result through uniq, and the output has the line once.
The pipe as defined, and as it runs
The lecture draws the pipe as "command 1, output, input, command 2" and says that the pipe passes the output of one command as input to another. POSIX states the definition used in the model section: for each command but the last, the shell connects the standard output of the command to the standard input of the next "as if by creating a pipe", and the exit status of the pipeline is the exit status of its last command (POSIX.1-2017, Shell Command Language §2.9.2). POSIX.1-2024 adds the pipefail option to §2.9.2: with the option enabled, the status is zero if all commands returned 0, and otherwise the status of the rightmost command that returned a non-zero status. POSIX also states that the shell waits for the last command and "may also wait for all commands". The composition of the model section therefore describes data and not time. In Linux the commands run at the same time, and a pipe is a buffer of limited capacity: a writer blocks when it is full, a reader blocks when it is empty, and a write to a pipe that no process reads from raises SIGPIPE (pipe(7)). Since Linux 2.6.11 the capacity is 16 pages of memory unless it is changed, which is 65,536 bytes with the 4096-byte pages of this machine (pipe(7); pages are defined in the memory section). Standard error is not part of the pipe unless redirected with 2>&1.
The shell script below checks these statements and the sorting rules. Section 1 pipes the first \(10^{8}\) integers from seq into head -n 3: if the pipeline ran stage after stage, it would first produce 100 million lines; it finishes at once because head exits after three lines and seq is killed by SIGPIPE when it writes again. The statuses are 141 for seq (\(128+13\)) and 0 for head, and the status of the whole pipeline is the status of the last command unless pipefail is set (set -o pipefail is in Bash and, since POSIX.1-2024, in §2.9.2 of the standard; PIPESTATUS is a Bash array and not part of POSIX). Section 2 shows that a pipe carries only standard output. Sections 3 and 4 test uniq and the two numeric sorts on four residuals. Section 5 shows the three exit statuses of grep: 0 when a line is selected, 1 when none is, 2 on an error (GNU grep manual, §2.3). Sections 6 and 7 test the leftmost-longest rule and the BRE and ERE differences. Section 8 tests the lecture's grep -r "pattern" *. Section 9 shows the back-reference of the previous section, and section 10 prints the capacity of a pipe. The check is exact.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
echo "== 1. the stages of a pipeline run at the same time"
seq 1 100000000 | head -n 3
echo "statuses of seq and head: ${PIPESTATUS[@]}"
seq 1 100000000 | head -n 3 > /dev/null
echo "pipeline status without pipefail: $?"
set -o pipefail
seq 1 100000000 | head -n 3 > /dev/null
echo "pipeline status with pipefail: $?"
set +o pipefail
echo "== 2. a pipe carries standard output only"
noisy() { echo "to stdout"; echo "to stderr" >&2; }
{ noisy | wc -l; } 2>&1
{ noisy 2>&1 | wc -l; } 2>&1
echo "== 3. uniq removes adjacent duplicates only"
printf 'mango\napple\nmango\ngreen\n' > fruit.txt
echo "-- uniq fruit.txt"; uniq fruit.txt
echo "-- sort fruit.txt | uniq"; sort fruit.txt | uniq
echo "-- sort -u fruit.txt"; sort -u fruit.txt
echo "-- sort fruit.txt | uniq -c"; sort fruit.txt | uniq -c
echo "== 4. numeric order of residuals"
printf '9.5e-05\n1.2e-03\n4.0e-05\n1.3e-06\n' > res.txt
echo "-- sort -n (reads the mantissa only)"; sort -n res.txt
echo "-- sort -g (reads the exponent)"; sort -g res.txt
echo "== 5. exit status of grep: 0 match, 1 no match, 2 error"
printf 'iter 50 residual 3.9e-03\n' > one.log
grep -q iter one.log; echo "pattern present: $?"
grep -q ERROR one.log; echo "pattern absent: $?"
grep -q iter missing.log 2> /dev/null; echo "file missing: $?"
echo "== 6. leftmost-longest in grep, leftmost-first in Python"
echo abcd | grep -oE 'ab|abcd'
python3 -c "import re; print(re.search('ab|abcd', 'abcd').group())"
echo "== 7. BRE and ERE"
echo aab | grep -o 'a+b'; echo "BRE a+b exit status: $?"
echo aab | grep -oE 'a+b'
echo aab | grep -o 'a\+b'
echo "== 8. a glob skips dot files, the directory name does not"
mkdir -p tree/sub; echo needle > tree/shown.txt; echo needle > tree/.hidden.txt; echo needle > tree/sub/deep.txt
cd tree
echo "-- grep -r needle *"; grep -r needle * | sort
echo "-- grep -r needle ."; grep -r needle . | sort
cd ..
echo "== 9. a back-reference recognizes squares ww, which no regular expression can"
printf 'abab\nabba\naa\nabc\nabcabc\n' | grep -E '^(.+)\1$'
echo "== 10. capacity of a pipe in bytes"
python3 -c "import os, fcntl; r, w = os.pipe(); print(fcntl.fcntl(w, 1032))"
== 1. the stages of a pipeline run at the same time
1
2
3
statuses of seq and head: 141 0
pipeline status without pipefail: 0
pipeline status with pipefail: 141
== 2. a pipe carries standard output only
to stderr
1
2
== 3. uniq removes adjacent duplicates only
-- uniq fruit.txt
mango
apple
mango
green
-- sort fruit.txt | uniq
apple
green
mango
-- sort -u fruit.txt
apple
green
mango
-- sort fruit.txt | uniq -c
1 apple
1 green
2 mango
== 4. numeric order of residuals
-- sort -n (reads the mantissa only)
1.2e-03
1.3e-06
4.0e-05
9.5e-05
-- sort -g (reads the exponent)
1.3e-06
4.0e-05
9.5e-05
1.2e-03
== 5. exit status of grep: 0 match, 1 no match, 2 error
pattern present: 0
pattern absent: 1
file missing: 2
== 6. leftmost-longest in grep, leftmost-first in Python
abcd
ab
== 7. BRE and ERE
BRE a+b exit status: 1
aab
aab
== 8. a glob skips dot files, the directory name does not
-- grep -r needle *
shown.txt:needle
sub/deep.txt:needle
-- grep -r needle .
./.hidden.txt:needle
./shown.txt:needle
./sub/deep.txt:needle
== 9. a back-reference recognizes squares ww, which no regular expression can
abab
aa
abcabc
== 10. capacity of a pipe in bytes
65536Each section confirms a statement and exposes a trap. In section 1 the three numbers appear immediately, and the statuses are 141 0; without pipefail the pipeline reports 0 and with it reports 141, so a script that enables pipefail and ends a pipeline with head will see failure statuses on success. In section 2 the first command prints to stderr on the terminal and counts one line; with 2>&1 inside the pipe the count is two. Section 3 shows uniq alone leaving mango twice, because the two lines are not adjacent; sort | uniq and sort -u print it once, and sort | uniq -c prints the count 2 beside it. Section 4 shows that sort -n orders 9.5e-05, 1.2e-03, 4.0e-05 and 1.3e-06 by their mantissas, placing the value \(1.2\times10^{-3}\) first although it is the largest, while sort -g returns them in numerical order. The consequence is concrete: for a residual log, the command that finds the smallest residual is sort -g | head -n 1, and sort -n gives a wrong answer without any error message. Section 5 returns the three statuses. In section 6, grep -o with the alternation ab|abcd prints abcd, the longest match at the leftmost position, and the matcher of Python's re module returns ab, the first alternative that succeeds. In section 7, the pattern a+b in BRE selects nothing, because + is an ordinary character there, and the exit status is 1; in ERE it matches aab, and a\+b matches it in BRE as the GNU extension. Section 8 shows what the lecture's command grep -r "Ved" * misses: the shell expands * to the names that do not begin with a dot, so a file named .hidden.txt is skipped, while grep -r needle . reads it. Without a file operand, grep -r searches the working directory (GNU grep manual, §2.1.6), so grep -r needle has the same effect as the form with .. Section 9 selects abab, aa and abcabc, the squares among the five input lines. Section 10 prints 65536.
Counting and selecting, on the running case
The lecture's last commands are wc, which prints the number of lines, words and bytes (4 11 61 for its file, and -l, -w and -c print one number each); head -2 and tail -2, which print the first and last two lines; and the names diff (compare line by line), paste (merge lines), tr (translate or delete characters) and sed (stream editor). The script lecture_files.sh of the awk section ran all of them on the lecture's files, in the second half of its output. The lecture's file for wc has the lines Mango is Yello, Apple is red, Mango is Yello and Green Vegetables. Typed exactly as shown, the file has 4 lines, 11 words and 60 bytes: \(14+12+14+16\) characters and 4 newlines. The slide's value 61 is one more. An invisible trailing blank or a different character in one word would explain it; the slide does not show which, and the discrepancy is recorded and not resolved. The lines, words and bytes agree.
The running case needs the commands in combination. The script below embeds the log of the first listing, so that it runs without the solver, and answers five questions with pipelines: how many progress lines there are, what the header and the final line say, which iteration and residual each progress line holds, which residuals are the smallest and the largest, and how the contraction factor over an interval of 50 sweeps is distributed. sed -n 's/…/…/p' prints only the lines on which the substitution happened; its pattern is a BRE with two groups, \(…\), which the replacement refers to as \1 and \2. The script is deterministic and the check is exact.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
# The log of listing 1 (N = 16), written here so that the script runs without the solver.
cat > solver.log <<'END'
# jacobi N=16 tol=1.0e-06 max_iter=20000
iter 50 residual 3.960505e-03
iter 100 residual 1.296030e-03
iter 150 residual 5.303838e-04
iter 200 residual 2.235469e-04
iter 250 residual 9.458274e-05
iter 300 residual 4.006077e-05
iter 350 residual 1.697280e-05
iter 400 residual 7.191545e-06
iter 450 residual 3.047196e-06
iter 500 residual 1.291163e-06
# converged iter=515 residual=9.979422e-07
END
echo "== lines by kind"
grep -c '^iter' solver.log
grep '^#' solver.log
echo "== iteration and residual of every progress line, with sed"
sed -n 's/^iter *\([0-9]*\) residual \(.*\)$/\1 \2/p' solver.log | head -n 3
echo "== the residual column, smallest and largest by value"
grep '^iter' solver.log | awk '{print $4}' | sort -g | sed -n '1p;$p'
echo "== summary in one pass of awk"
awk '/^iter/ { n++; if (n == 1) first = $4; last = $4 }
END { printf "%d progress lines, first residual %s, last residual %s\n", n, first, last }' solver.log
echo "== contraction factor over each interval of 50 iterations, rounded to two places"
grep '^iter' solver.log | awk 'NR > 1 { printf "%.2f\n", $4 / prev } { prev = $4 }' | sort | uniq -c
echo "== the last three progress lines"
grep '^iter' solver.log | tail -n 3
== lines by kind
10
# jacobi N=16 tol=1.0e-06 max_iter=20000
# converged iter=515 residual=9.979422e-07
== iteration and residual of every progress line, with sed
50 3.960505e-03
100 1.296030e-03
150 5.303838e-04
== the residual column, smallest and largest by value
1.291163e-06
3.960505e-03
== summary in one pass of awk
10 progress lines, first residual 3.960505e-03, last residual 1.291163e-06
== contraction factor over each interval of 50 iterations, rounded to two places
1 0.33
1 0.41
7 0.42
== the last three progress lines
iter 400 residual 7.191545e-06
iter 450 residual 3.047196e-06
iter 500 residual 1.291163e-06The log has 10 progress lines and the two comment lines that begin with #. The sed command turns iter 50 residual 3.960505e-03 into 50 3.960505e-03. The smallest residual is \(1.291163\times10^{-6}\), at the last progress line, and the largest is \(3.960505\times10^{-3}\), at the first. The ratios in the next block are all below 1, so the residual falls monotonically in this log. The one-pass awk summary reports the same two values and the count. The last two blocks lead to the next section. The ratio of consecutive progress residuals, rounded to two places, is 0.33 once, 0.41 once and 0.42 seven times, so it settles at about 0.42 per 50 sweeps. That is a per-sweep factor of \(0.42^{1/50}=0.9828\), a number that the next section derives from the grid.
From the residual history to the convergence rate
The question a person asks of a residual history is when the run will end. This section answers it for the running case in three steps: a closed form for the rate at which the iteration converges, an estimator of that rate from the log, and a test of both against the logs of \(N=8,16,32\) and later of larger runs. The section is an original construction; the only external input is the value of the rate, which Demmel's 1996 Berkeley lecture notes state and which is derived here.
The eigenmodes of the iteration
Let \(u^{k}\) be the interior values after \(k\) sweeps and \(u^{*}\) the fixed point of the iteration, that is, the discrete solution of the Laplace problem with the stated boundary values. A sweep is \(u^{k+1}_{ij}=\tfrac14\bigl(u^{k}_{i-1,j}+u^{k}_{i+1,j}+u^{k}_{i,j-1}+u^{k}_{i,j+1}\bigr)\) for \(i,j=1,\dots,N\). Boundary values enter as constants and are the same for \(u^{k}\) and \(u^{*}\), so the error \(e^{k}=u^{k}-u^{*}\) obeys the same averaging with zero boundary values: \(e^{k+1}=Be^{k}\), where \(B\) is the linear map that averages the four neighbours and treats the boundary as zero. Let \(\theta=\pi/(N+1)\). For integers \(s,t\in\{1,\dots,N\}\) define \(v^{(s,t)}_{ij}=\sin(s\,i\theta)\sin(t\,j\theta)\). The trigonometric identity \(\sin(s(i-1)\theta)+\sin(s(i+1)\theta)=2\cos(s\theta)\sin(s\,i\theta)\) holds for every \(i\), and at \(i=0\) and \(i=N+1\) the sine is zero, which is the zero boundary condition. Applying the averaging to \(v^{(s,t)}\) therefore gives
\[ Bv^{(s,t)}=\mu_{st}\,v^{(s,t)},\qquad \mu_{st}=\tfrac12\bigl(\cos s\theta+\cos t\theta\bigr). \tag{4.3} \]The \(N^{2}\) vectors \(v^{(s,t)}\) are products of the one-dimensional sine vectors, which are a basis of \(\mathbb R^{N}\), so they are a basis of the space of interior grids. Expand the initial error \(e^{0}=-u^{*}\) as \(e^{0}=\sum c_{st}v^{(s,t)}\). Then \(e^{k}=\sum c_{st}\mu_{st}^{k}v^{(s,t)}\). Every \(\mu_{st}\) lies strictly between \(-1\) and 1, and the one of largest magnitude is attained at \(s=t=1\) and, with the opposite sign, at \(s=t=N\):
\[ \rho=\max_{s,t}|\mu_{st}|=\cos\frac{\pi}{N+1}. \tag{4.4} \]This is the value stated by Demmel (CS267 lecture notes of 1996, on the discrete Poisson equation: \(\rho_{\mathrm{Jacobi}}(n)=\cos(\pi/(n+1))\)), for the error in the root-sum-of-squares norm. For large \(N\), \(\rho\approx1-\pi^{2}/(2(N+1)^{2})\), so the factor tends to 1 as the grid is refined, and the number of sweeps for a fixed reduction grows in proportion to \(N^{2}\).
The solver logs the change per sweep, which it calls the residual. The change in one sweep is \(d^{k}=u^{k+1}-u^{k}=e^{k+1}-e^{k}=\sum c_{st}(\mu_{st}-1)\mu_{st}^{k}v^{(s,t)}\), and the residual logged after \(k+1\) sweeps is \(r_{k+1}=\max_{ij}|d^{k}_{ij}|\). The change per sweep is a scaled residual of the linear system. Write the discrete problem as \(\mathsf Au=b\), with 4 on the diagonal of \(\mathsf A\), \(-1\) for each interior neighbour, and the boundary values in \(b\). Then \(B=I-\tfrac14\mathsf A\), one sweep is \(u^{k+1}=u^{k}+\tfrac14(b-\mathsf Au^{k})\), and \(d^{k}=\tfrac14(b-\mathsf Au^{k})\). The logged \(r_{k+1}\) is one quarter of \(\lVert b-\mathsf Au^{k}\rVert_\infty\), so the name is exact up to the factor 4, and a log of the system residual has the same factor \(\rho\). Each mode keeps its eigenvalue, so the modes with \(|\mu|\) smaller than \(\rho\) die out faster than the leading one. The expansion therefore predicts
\[ r_{k}\approx A\rho^{k}\quad\text{for large }k,\qquad A=\frac{|c_{11}|\,(1-\rho)\,\max_{ij}|v^{(1,1)}_{ij}|}{\rho}\propto(1-\rho), \tag{4.5} \]where the factor \(1/\rho\) comes from the index shift \(r_k=\max|d^{k-1}|\). The mode \(s=t=N\) has the eigenvalue \(-\rho\), the same decay factor in magnitude with alternating sign; its coefficient vanishes for even \(N\), as the check below shows. Equation (4.5) states an asymptote and a proportionality. It does not say after how many sweeps the asymptote is reached.
Estimating the factor and the end of the run from the log
For two logged points \((k_1,r_1)\) and \((k_2,r_2)\) with \(k_2\gt k_1\), define the observed factor per sweep \(\hat\rho=(r_2/r_1)^{1/(k_2-k_1)}\). This is the geometric mean of the ratios of consecutive sweeps, and equation (4.5) predicts \(\hat\rho\to\rho\) when both points lie in the asymptotic range. With the exact \(\rho\) known, the sweep at which the run ends follows from solving \(r_{k}=\mathrm{tol}\) with \(r_1\) as the base point:
\[ k_{\mathrm{end}}\approx k_1+\frac{\ln(\mathrm{tol}/r_1)}{\ln\rho}, \qquad \ln\rho=\ln\cos\frac{\pi}{N+1}. \tag{4.6} \]Two estimates of \(\hat\rho\) are of interest: \(\hat\rho_{\mathrm{window}}\), computed from the first and last progress line, and \(\hat\rho_{\mathrm{last}}\), computed from the last two. The first uses points that include the transient, and the second uses points in the asymptotic range. The script below embeds three real logs, written by the solver of the first listing for \(N=8\) (a progress line every 25 sweeps), \(N=16\) (every 50) and \(N=32\) (every 100), and computes for each log both estimates, \(\rho\) from (4.4), the relative error of \(\hat\rho_{\mathrm{last}}\), the sweep at which the run converged and the sweep predicted by (4.6) from the last and from the first progress line, with \(\rho\) in (4.6); Exercise 6 uses the estimate \(\hat\rho_{\mathrm{last}}\) instead. The check is exact.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
# Logs written by jacobi_log (listing above) for N = 8, 16 and 32.
cat > log8.txt <<'END'
# jacobi N=8 tol=1.0e-06 max_iter=20000
iter 25 residual 5.541889e-03
iter 50 residual 1.108191e-03
iter 75 residual 2.328766e-04
iter 100 residual 4.915472e-05
iter 125 residual 1.037992e-05
iter 150 residual 2.191985e-06
# converged iter=163 residual=9.764570e-07
END
cat > log16.txt <<'END'
# jacobi N=16 tol=1.0e-06 max_iter=20000
iter 50 residual 3.960505e-03
iter 100 residual 1.296030e-03
iter 150 residual 5.303838e-04
iter 200 residual 2.235469e-04
iter 250 residual 9.458274e-05
iter 300 residual 4.006077e-05
iter 350 residual 1.697280e-05
iter 400 residual 7.191545e-06
iter 450 residual 3.047196e-06
iter 500 residual 1.291163e-06
# converged iter=515 residual=9.979422e-07
END
cat > log32.txt <<'END'
# jacobi N=32 tol=1.0e-06 max_iter=20000
iter 100 residual 2.324855e-03
iter 200 residual 9.689871e-04
iter 300 residual 5.182180e-04
iter 400 residual 3.082425e-04
iter 500 residual 1.916505e-04
iter 600 residual 1.209935e-04
iter 700 residual 7.673716e-05
iter 800 residual 4.870428e-05
iter 900 residual 3.092399e-05
iter 1000 residual 1.963854e-05
iter 1100 residual 1.247287e-05
iter 1200 residual 7.922195e-06
iter 1300 residual 5.031943e-06
iter 1400 residual 3.196182e-06
iter 1500 residual 2.030159e-06
iter 1600 residual 1.289526e-06
# converged iter=1657 residual=9.955969e-07
END
awk '
function report( rho, rwin, rlast, kpred, kfirst) {
if (!n) return
rho = cos(atan2(0, -1) / (N + 1))
rwin = (r1 / r0) ^ (1 / (k1 - k0))
rlast = (r1 / rp) ^ (1 / (k1 - kp))
kpred = k1 + log(tol / r1) / log(rho)
kfirst = k0 + log(tol / r0) / log(rho)
printf "%3d %6d %14.6f %13.6f %10.6f %14.5f%% %9d %9.1f %10.1f\n", N, n, rwin, rlast, rho, 100 * (rlast - rho) / rho, kconv, kpred, kfirst
}
FNR == 1 { report(); n = 0 }
/^# jacobi/ { split($3, a, "="); N = a[2]; split($4, b, "="); tol = b[2] }
/^iter/ { if (!n++) { k0 = $2; r0 = $4 } kp = k1; rp = r1; k1 = $2; r1 = $4 }
/^# converged/ { split($3, a, "="); kconv = a[2] }
END { report() }
' log8.txt log16.txt log32.txt | { printf "%3s %6s %14s %13s %10s %15s %9s %9s %10s\n" N points rho_hat_window rho_hat_last rho rel_error_last converged from_last from_first; cat; }
N points rho_hat_window rho_hat_last rho rel_error_last converged from_last from_first
8 6 0.939242 0.939692 0.939693 -0.00002% 163 162.6 163.6
16 10 0.982317 0.982973 0.982973 -0.00000% 515 514.9 532.4
32 16 0.995014 0.995472 0.995472 -0.00000% 1657 1656.0 1808.0The factor \(\hat\rho_{\mathrm{last}}\) equals \(\rho\) to the six printed digits for \(N=16\) and \(N=32\), and agrees to \(2\times10^{-7}\) in relative terms for \(N=8\) (0.939692 against 0.939693). The estimate \(\hat\rho_{\mathrm{window}}\) is lower than \(\rho\) by 0.05 % to 0.07 %, because the early points contain modes that decay faster than the leading one. A small error in \(\hat\rho\) is a larger error in the quantity that matters, the distance of the factor from 1. For \(N=16\), \(1-\hat\rho_{\mathrm{window}}=0.017683\) and \(1-\rho=0.017027\), so the window estimate overstates the rate of convergence by 3.9 %. The prediction (4.6) from the last progress line is 162.6, 514.9 and 1656.0 sweeps against the observed 163, 515 and 1657: it is within one sweep in all three runs. The last progress line lies 13, 15 and 57 sweeps before the end in the three runs, so that prediction extrapolates a short distance. With the exact \(\rho\), (4.6) predicts well only from a base point in the asymptotic range. From the first progress line, in the last column, it overestimates the end by 0.4 %, 3.4 % and 9.1 % for \(N=8,16,32\), whose first lines lie at 15 %, 10 % and 6 % of the run, and by 8.5 % for \(N=64\), with the first line at 9.5 % of the run (Exercise 6). A factor estimated from early lines errs in the other direction: the faster modes make it too small, and the predicted end comes too early (the \(N=1000\) run below).
The prediction (4.5) can also be tested on the values themselves and not only on their ratios. The program below solves the discrete Laplace problem for \(N=16\) exactly with a linear solve, expands \(e^{0}=-u^{*}\) in the modes of (4.3) by the orthogonality of the one-dimensional sine vectors, evaluates the modal formula for \(d^{k-1}\) at \(k=50,150,250,350,450\) (the logged iterations), and prints the maximum absolute entry beside the logged residual. The check is exact.
"""Predict the residual log of the Jacobi run (N = 16) from the eigenmodes of the iteration."""
import numpy as np
N = 16
theta = np.pi / (N + 1)
i = np.arange(1, N + 1)
S = np.sin(np.outer(i, np.arange(1, N + 1)) * theta) # S[i-1, p-1] = sin(p i theta)
mu = 0.5 * (np.cos(np.arange(1, N + 1) * theta)[:, None] + np.cos(np.arange(1, N + 1) * theta)[None, :])
# Exact solution u* of the discrete Laplace problem: u = 1 on the top edge (row 0), 0 on the other edges.
A = np.zeros((N * N, N * N)); b = np.zeros(N * N)
for r in range(N):
for c in range(N):
k = r * N + c
A[k, k] = 4.0
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
rr, cc = r + dr, c + dc
if 0 <= rr < N and 0 <= cc < N:
A[k, rr * N + cc] = -1.0
elif rr < 0:
b[k] += 1.0 # the neighbour is on the top edge
ustar = np.linalg.solve(A, b).reshape(N, N)
# Initial error e0 = u0 - u* = -u*; coefficients in the sine basis (S is orthogonal up to a factor).
c = (2.0 / (N + 1)) ** 2 * S.T @ (-ustar) @ S
print(f"rho = cos(pi/{N + 1}) = {np.cos(theta):.6f}; largest |mu| = {np.abs(mu).max():.6f}")
print("coefficient of the mode s = t = N below 1e-12 in magnitude:", "yes" if abs(c[-1, -1]) < 1e-12 else "no")
print("iteration residual in the log residual from the modes ratio")
log = {50: 3.960505e-03, 150: 5.303838e-04, 250: 9.458274e-05, 350: 1.697280e-05, 450: 3.047196e-06}
for k, logged in log.items():
# residual after k sweeps is max |u^k - u^(k-1)| = max |e^k - e^(k-1)|
coef = c * mu ** (k - 1) * (mu - 1.0)
d = S @ coef @ S.T
print(f"{k:9d} {logged:21.6e} {np.abs(d).max():25.6e} {np.abs(d).max() / logged:8.5f}")
# The residual bounds the change per sweep, not the error: at the sweep where the run stops,
# the error is about r / (1 - rho) for the leading mode.
k, logged = 515, 9.979422e-07
err = np.abs(S @ (c * mu ** k) @ S.T).max()
print(f"at the stop (sweep {k}): residual {logged:.3e}, error from the modes {err:.3e}, "
f"residual/(1-rho) {logged / (1 - np.cos(theta)):.3e}")
rho = cos(pi/17) = 0.982973; largest |mu| = 0.982973
coefficient of the mode s = t = N below 1e-12 in magnitude: yes
iteration residual in the log residual from the modes ratio
50 3.960505e-03 3.960505e-03 1.00000
150 5.303838e-04 5.303838e-04 1.00000
250 9.458274e-05 9.458274e-05 1.00000
350 1.697280e-05 1.697280e-05 1.00000
450 3.047196e-06 3.047196e-06 1.00000
at the stop (sweep 515): residual 9.979e-07, error from the modes 5.761e-05, residual/(1-rho) 5.861e-05The two columns agree in every printed digit at all five logged iterations, and the ratio is 1.00000 in every row. In exact arithmetic the agreement is an identity, so the check tests the C solver, the modal program and the rounding, not a modelling assumption. The single-mode line \(A\rho^{k}\) of (4.5), with \(A\) fixed at the last logged point, does not agree: at \(k=50\) it gives \(2.93\times10^{-3}\), which is 26 % below the logged \(3.96\times10^{-3}\). The full expansion fits because it contains every mode. The program also tests a symmetry stated above: for \(N=16\) the coefficient of the mode \(s=t=N\) is below \(10^{-12}\) in magnitude (it is of the order of \(10^{-18}\) in a separate run, for \(N=16\) and \(N=32\)). The reason is that \(u^{*}\) is symmetric about the vertical midline of the grid and the mode with \(t=N\) even is antisymmetric about it. For odd \(N\) the argument does not apply and the chapter does not test it.
The end of the run follows from the amplitude of (4.5). Solving \(A\rho^{k}=\mathrm{tol}\) gives
\[ k_{\mathrm{end}}\approx\frac{\ln(A/\mathrm{tol})}{-\ln\rho},\qquad A\approx a\,(1-\rho),\quad a=\frac{4}{\pi^{2}}. \tag{4.7} \]The amplitude \(A\), computed from the last logged point as \(r\rho^{-k}\), is 0.0247, 0.00692, 0.00184 and 0.000473 for \(N=8,16,32,64\). The quotient \(A/(1-\rho)\) is 0.410, 0.406, 0.406 and 0.405, constant within 1.1 %, as the proportionality \(A\propto1-\rho\) of (4.5) predicts. The limit has a closed form. As \(N\) grows, \(|c_{11}|\) tends to the coefficient of \(\sin\pi x\sin\pi y\) in the continuous solution, with \(x=ih\) the distance from the top edge and \(y=jh\), \(h=1/(N+1)\): the edge value 1 has the sine coefficient \(4/\pi\), and the profile \(\sinh(\pi(1-x))/\sinh\pi\) projects onto \(\sin\pi x\) with coefficient \(1/\pi\), so \(|c_{11}|\to4/\pi^{2}=0.40528\), and \(\max|v^{(1,1)}|/\rho\to1\). The exact discrete values of \(|c_{11}|\) are 0.39708, 0.40298, 0.40467 and 0.40513 for \(N=8,16,32,64\). Since \(1-\rho\) falls by a factor of 3.5 to 3.9 at each doubling of \(N\), so does \(A\), and \(\ln(A/\mathrm{tol})\) falls from 10.1 to 8.8, 7.5 and 6.2. This explains the observed iteration counts 163, 515, 1657 and 5272: they grow by factors of 3.16, 3.22 and 3.18 at each doubling, and not by the factors 3.6, 3.8 and 3.9 that \((N+1)^{2}\) alone would give, because the shrinking amplitude removes part of the work. Equation (4.7) with \(a=4/\pi^{2}\) therefore predicts the end of a run from \(N\) alone, before the run, without a fitted constant. The program below tests that prediction. It runs the same iteration with NumPy (the arithmetic of one sweep is the same as in the C solver, and the sweep counts for \(N=8,16,32,64\) equal those of the C logs) and compares the observed stopping sweep with (4.7) for \(N=8,16,32,64\) and \(N=100\). It also prints \(\mathrm{tol}/(1-\rho)\), the estimate of the error at the stop that (4.8) below justifies. The check is exact.
"""Predict the sweep at which the Jacobi run stops from N alone, and compare with the run.
The prediction is k_end = ln(a (1 - rho) / tol) / (-ln rho) with rho = cos(pi/(N+1)) and a = 4/pi^2 = 0.40528,
the limit of the quotient A/(1 - rho). The runs use NumPy; the arithmetic of one
sweep is the same as in the C solver, so the sweep counts are the same.
"""
import math
import numpy as np
TOL, A_OVER = 1.0e-6, 4.0 / math.pi ** 2
def sweeps(N):
u = np.zeros((N + 2, N + 2)); u[0, :] = 1.0
unew = u.copy()
k, r = 0, 1.0
while r >= TOL:
unew[1:-1, 1:-1] = 0.25 * (u[:-2, 1:-1] + u[2:, 1:-1] + u[1:-1, :-2] + u[1:-1, 2:])
r = np.abs(unew[1:-1, 1:-1] - u[1:-1, 1:-1]).max()
u, unew = unew, u
k += 1
return k
print(" N observed predicted difference tol/(1-rho), estimated error at the stop")
for N in (8, 16, 32, 64, 100):
rho = math.cos(math.pi / (N + 1))
pred = math.log(A_OVER * (1 - rho) / TOL) / -math.log(rho)
k = sweeps(N)
print(f"{N:4d} {k:9d} {pred:10.1f} {100 * (pred - k) / k:10.2f} % {TOL / (1 - rho):12.2e}")
N observed predicted difference tol/(1-rho), estimated error at the stop
8 163 162.4 -0.34 % 1.66e-05
16 515 514.7 -0.06 % 5.87e-05
32 1657 1655.9 -0.07 % 2.21e-04
64 5272 5271.6 -0.01 % 8.56e-04
100 10910 10909.4 -0.01 % 2.07e-03The prediction is within 0.34 % of the observed stopping sweep for \(N=8\), within 0.07 % for \(N=16\) and 32, and within 0.01 % for \(N=64\) and for \(N=100\): 10,909.4 predicted against 10,910 observed. Three runs of the C solver outside the code lab, with the iteration limit raised, extend the test to larger grids. They stopped at sweep 31,946 for \(N=200\), 106,269 for \(N=500\) and 191,001 for \(N=1000\), and (4.7) gives 31,944.4, 105,563.4 and 140,335.8, which is 0.005 %, 0.66 % and 26.5 % below. The prediction degrades as the ratio \(A/\mathrm{tol}=a(1-\rho)/\mathrm{tol}\) falls: that ratio is 49.5, 8.0 and 2.0 for the three grids. When it is near 1, the leading mode alone crosses the tolerance after only \(\ln(A/\mathrm{tol})/(1-\rho)\) sweeps, a time at which the faster modes have not yet died out; (4.7) assumes that they have.
The N = 1000 run
The run for \(N=1000\) tests the modal description at a size where the transient dominates. It took 634 s, 3.3 ms per sweep, and wrote 19 progress lines. Its residuals fall as \(1/k\) at first (\(2.42\times10^{-5}\), \(1.21\times10^{-5}\) and \(8.06\times10^{-6}\) at sweeps 10,000, 20,000 and 30,000) and only later approach a geometric decay, so a person who read the factor \(\hat\rho\) from the first lines would predict a much shorter run. The program below copies eight of the logged residuals, computes the exact discrete solution \(u^{*}\) from its sine series in \(j\) and its hyperbolic profile in \(i\), expands \(e^{0}=-u^{*}\) in the modes, and evaluates the residual after each logged sweep from the expansion. It also evaluates the error at the stopping sweep and the residual that the leading mode alone would give there. The program holds \(10^{6}\) modes; its matrix products take about 15 s on this machine, and the check is exact.
"""Predict the residual log of the N = 1000 Jacobi run from the eigenmodes, and the error at its stop.
The logged residuals are copied from one run of the C solver (jacobi_log.c with the iteration limit
raised to 2,000,000 and a progress line every 10,000 sweeps), which took 10.6 minutes.
"""
import numpy as np
N = 1000
LOG = {10000: 2.419687e-05, 20000: 1.209857e-05, 30000: 8.064885e-06, 50000: 4.824432e-06,
100000: 2.297740e-06, 150000: 1.394993e-06, 190000: 1.007588e-06, 191001: 9.999952e-07}
theta = np.pi / (N + 1)
n = np.arange(1, N + 1)
S = np.sin(np.outer(n, n) * theta) # S[i-1, p-1] = sin(p i theta)
cosq = np.cos(n * theta)
# Exact discrete solution u*: sine series in j, hyperbolic profile in i (the top edge is i = 0).
g = (2.0 / (N + 1)) * S.sum(axis=0) # sine coefficients of the constant 1
tau = np.arccosh(2.0 - cosq) # cosh(tau) = 2 - cos(q theta)
i = n[:, None]
profile = np.exp(-i * tau) * (1 - np.exp(-2 * (N + 1 - i) * tau)) / (1 - np.exp(-2 * (N + 1) * tau))
ustar = (profile * g) @ S.T # ustar[i-1, j-1]
c = (2.0 / (N + 1)) ** 2 * S.T @ (-ustar) @ S # coefficients of e0 = -u*
mu = 0.5 * (cosq[:, None] + cosq[None, :])
print(f"N = {N}: rho = {np.cos(theta):.9f}, 1 - rho = {1 - np.cos(theta):.3e}")
print("sweep residual in the log residual from the modes ratio")
for k, logged in LOG.items():
d = S @ (c * (mu - 1.0) * mu ** (k - 1)) @ S.T # change of sweep k
r = np.abs(d).max()
print(f"{k:6d} {logged:22.6e} {r:25.6e} {r / logged:8.4f}")
k = 191001
err = np.abs(S @ (c * mu ** k) @ S.T).max()
print(f"error at sweep {k}: {err:.3f} residual/(1-rho): {LOG[k] / (1 - np.cos(theta)):.3f}")
lead = np.abs(np.outer(S[:, 0], S[:, 0]) * c[0, 0] * (mu[0, 0] - 1.0) * mu[0, 0] ** (k - 1)).max()
print(f"residual at sweep {k} from the leading mode alone: {lead:.3e}; from all modes: {LOG[k]:.3e}")
N = 1000: rho = 0.999995075, 1 - rho = 4.925e-06
sweep residual in the log residual from the modes ratio
10000 2.419687e-05 2.419687e-05 1.0000
20000 1.209857e-05 1.209857e-05 1.0000
30000 8.064885e-06 8.064885e-06 1.0000
50000 4.824432e-06 4.824432e-06 1.0000
100000 2.297740e-06 2.297740e-06 1.0000
150000 1.394993e-06 1.394993e-06 1.0000
190000 1.007588e-06 1.007588e-06 1.0000
191001 9.999952e-07 9.999952e-07 1.0000
error at sweep 191001: 0.167 residual/(1-rho): 0.203
residual at sweep 191001 from the leading mode alone: 7.792e-07; from all modes: 1.000e-06The modal residual equals the logged residual to the seven printed digits at all eight sweeps, from 10,000 to 191,001; the expansion was fitted to nothing in the log, and the log came from a different program. The error of the iterate at the stopping sweep is 0.167, so the run that the rule \(r\lt10^{-6}\) declared converged has a maximum error of 17 % of the boundary value 1. The estimate \(r/(1-\rho)\), derived as (4.8) in the next subsection, gives 0.203, 22 % above the exact value; at \(N=16\) it was 1.7 % above. The estimate is larger here because the faster modes still carry part of the residual: the leading mode alone gives \(7.79\times10^{-7}\) at the stopping sweep, and the other modes supply the remaining 22 % of the logged \(1.00\times10^{-6}\). That is the reason why (4.7) is 26.5 % low for \(N=1000\).
What the residual does not bound
The last column of the output of end_prediction.py states a consequence that the log hides. The stopping rule bounds the change per sweep, \(r_k\lt\mathrm{tol}\), and not the error \(\lVert u^{k}-u^{*}\rVert_{\infty}\). For the leading mode the change and the error are linked by the factor \(\mu-1\) of the expansion of \(d^{k}\): \(d^{k}=(\mu_{11}-1)e^{k}\), so
Equation (4.8) is an estimate, not a bound. Two exact statements hold. Since \(e^{k}=-(I-B)^{-1}d^{k}\) and the eigenvalues of the symmetric map \(B\) lie in \([-\rho,\rho]\), the root-sum-of-squares norm satisfies \(\lVert e^{k}\rVert_{2}\le\lVert d^{k}\rVert_{2}/(1-\rho)\), with equality for the leading mode. In the max-norm the guaranteed constant is the largest row sum of \((I-B)^{-1}\), which is 23.15, 84.43, 320.18 and 1244.31 for \(N=8,16,32,64\), that is 1.40 to 1.45 times \(1/(1-\rho)\) (a computation made outside the code lab). A stopping rule that must guarantee \(\lVert e\rVert_\infty\lt\delta\) therefore needs \(\mathrm{tol}\approx\delta(1-\rho)/1.45\).
The factor \(1/(1-\rho)\approx2(N+1)^{2}/\pi^{2}\) grows with the square of \(N\). At the stopping sweep of the \(N=16\) run, the modal computation of the last line of modal_check.py gives an error of \(5.761\times10^{-5}\) against \(r/(1-\rho)=5.861\times10^{-5}\) from (4.8), which differ by 1.7 %. The error at the stop is therefore 58 times the tolerance for \(N=16\), and the last column of the output of end_prediction.py gives \(\mathrm{tol}/(1-\rho)=1.66\times10^{-5}\), \(5.87\times10^{-5}\), \(2.21\times10^{-4}\), \(8.56\times10^{-4}\) and \(2.07\times10^{-3}\) for \(N=8\) to 100. At \(N=1000\) the factor is \(2\times10^{5}\), and the run of the previous subsection stopped with an error of 0.167. To bring the error below \(\delta\), the tolerance on the change must be about \(\delta(1-\rho)\), and (4.7) then gives \(k_{\mathrm{end}}\approx\ln(a/\delta)/(-\ln\rho)\): for \(N=1000\) and \(\delta=10^{-6}\), \(\ln(4.053\times10^{5})/(4.925\times10^{-6})=2.62\times10^{6}\) sweeps, which is 2.4 hours at the 3.3 ms per sweep of the run above, against 191,001 sweeps for the rule \(r\lt10^{-6}\). The guaranteed max-norm constant of 1.45 changes that count by \(\ln1.45/(4.925\times10^{-6})=7.5\times10^{4}\) sweeps, about 3 %. The ratio \(A/\mathrm{tol}\) is \(a/\delta=4.05\times10^{5}\) in this case, so (4.7) is in its range of validity there. The error discussed here is the iteration error with respect to the discrete solution \(u^{*}\), not the discretization error of \(u^{*}\) as an approximation of the continuous solution. The relation (4.8) holds in the asymptotic range, where one mode dominates; it was tested at \(N=16\) (1.7 % above the exact error) and at \(N=1000\) (22 % above), and the second test is outside the asymptotic range.
The boundary of the result is the problem. The closed form (4.4) holds for the Jacobi iteration on a square grid with equal spacing in both directions and constant Dirichlet values on each edge. Gauss–Seidel has the factor \(\rho^{2}\) (Demmel), and conjugate gradients do not converge at a constant factor. The estimator \(\hat\rho\) assumes a log in which the residual is the same measure at every line. A log that mixes measures, for instance the change per sweep on some lines and \(\lVert b-\mathsf Au^{k}\rVert_\infty\), four times larger for Jacobi, on others, gives wrong ratios across the switch. The cost of the run follows from (4.4): the number of sweeps grows with \(N^{2}\), and the work per sweep also grows with \(N^{2}\), so the total work grows with \(N^{4}\), a fact that returns in chapter 9.
Memory: virtual and resident size, and what free reports W1L6 0:06
The lecture lists the concepts of Linux memory management on a slide: physical memory, the actual hardware memory; virtual memory, "an abstraction that allows processes to use more memory than the physically available RAM"; swap space, disk space reserved for pages when physical memory runs out, slower than RAM; and paging, the division of memory into fixed-size chunks called pages. It then names five commands: free (RAM and swap usage), vmstat (virtual memory statistics), df (disk space usage), swapon (show, enable or disable swap space) and meminfo (detailed memory information). The lecture shows no output of these commands. This section supplies the definitions that the output needs, and tests them on the running case.
Virtual size and resident size
A process addresses virtual memory: a set of mappings from ranges of virtual addresses to storage. The kernel divides memory into pages, 4096 bytes on this machine (the machine listing prints it). A page that is present in RAM is resident. The kernel reports two sizes per process in /proc/PID/status: VmSize, the size of the virtual address space, and VmRSS, the resident set size, which is the sum of the lines RssAnon, RssFile and RssShmem. The manual marks the values as inaccurate, because of a kernel-internal scalability optimization, and names /proc/PID/smaps and /proc/PID/smaps_rollup as the slower, accurate sources (proc_pid_status(5), proc_pid_statm(5)). The two sizes differ because the kernel allocates RAM for an anonymous mapping, the kind that malloc uses for a large request, only when a page is first written, which is called demand paging. A program can therefore hold a large virtual size and a small resident size. The slide's statement that virtual memory lets a process use more memory than the physical RAM follows from this: a process may map more than it ever touches, and the kernel may move rarely used pages to swap. Virtual memory also gives each process a private address space, which the slide does not mention.
The prediction for the running case is simple. The solver holds two grids of \((N+2)^{2}\) doubles, which is \(16(N+2)^{2}\) bytes. For \(N=16\) that is 5184 bytes, the number on the diagnostic line of the solver. For \(N=1000\) it is 16,064,064 bytes (15.3 MiB), and for \(N=4000\) it is 256,256,064 bytes (244.4 MiB). The program below allocates the two grids of \(N=4000\) with malloc and reads VmSize and VmRSS before the allocation, after it, and after it has written every element once. The stores go through a pointer to volatile double, because otherwise the compiler removes the allocation and the stores, and the program measures nothing. The output is deterministic at the resolution that the program prints, and the check is exact. The program checks, in its last line, that the growth of VmRSS is within 1 MiB of the prediction.
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Read one "Name: value kB" line of /proc/self/status; return the value in kB. */
static long status_kb(const char *name)
{
char line[256];
long value = -1;
FILE *f = fopen("/proc/self/status", "r");
if (!f) return -1;
size_t len = strlen(name);
while (fgets(line, sizeof line, f))
if (strncmp(line, name, len) == 0 && line[len] == ':') value = atol(line + len + 1);
fclose(f);
return value;
}
int main(void)
{
const int N = 4000;
size_t cells = (size_t)(N + 2) * (N + 2);
double predicted_mib = 2.0 * cells * sizeof(double) / (1024.0 * 1024.0);
printf("prediction: 2 x %d x %d x 8 bytes = %.1f MiB\n", N + 2, N + 2, predicted_mib);
long size0 = status_kb("VmSize"), rss0 = status_kb("VmRSS");
double *u = malloc(cells * sizeof *u), *unew = malloc(cells * sizeof *unew);
long size1 = status_kb("VmSize"), rss1 = status_kb("VmRSS");
volatile double *pu = u, *pn = unew; /* volatile: the compiler must perform every store */
for (size_t i = 0; i < cells; i++) { pu[i] = 0.0; pn[i] = 0.0; } /* first touch of every page */
long size2 = status_kb("VmSize"), rss2 = status_kb("VmRSS");
printf("after malloc: VmSize +%4ld MiB VmRSS +%4ld MiB\n",
lround((size1 - size0) / 1024.0), lround((rss1 - rss0) / 1024.0));
printf("after first touch: VmSize +%4ld MiB VmRSS at %ld %% of the prediction\n",
lround((size2 - size0) / 1024.0), lround(100.0 * (rss2 - rss0) / 1024.0 / predicted_mib));
printf("growth of VmRSS within 1 MiB of the prediction: %s\n",
fabs((rss2 - rss0) / 1024.0 - predicted_mib) < 1.0 ? "yes" : "no");
return 0;
}
prediction: 2 x 4002 x 4002 x 8 bytes = 244.4 MiB
after malloc: VmSize + 244 MiB VmRSS + 0 MiB
after first touch: VmSize + 244 MiB VmRSS at 100 % of the prediction
growth of VmRSS within 1 MiB of the prediction: yesThe allocation raises VmSize by 244 MiB and leaves VmRSS unchanged at the printed resolution. The first write to every page raises VmRSS to 100 % of the prediction, rounded to whole percent (a growth between 243.2 and 245.6 MiB), and the last line of the output records that the growth is within 1 MiB of 244.4 MiB. The program prints a percentage and not whole mebibytes because the measured growth lies close to the rounding boundary 244.5 MiB, and a rounded value would change from run to run. The prediction therefore holds for an anonymous allocation of known size, and the resident size is the quantity to compare with a memory limit. Which pages are touched first also decides where a multi-socket machine places them, a point that chapters 7 and 21 take up. A person who plans a run uses \(16(N+2)^{2}\) bytes as a lower bound. For the sample value of 15,207.1 MiB of available memory on this machine (the available row of the next listing, from /proc/meminfo), the two grids fit up to \(N=31{,}567\), and the lecture's machine, with 2,500,528 KiB available on its top screen, fits \(N\) up to 12,648 under the same rule; exercise 2 asks for the computation. The rule counts the grids only and ignores the program, the log and the other processes.
The columns of free
The lecture's free shows total, used, free, shared, buffers/cache and available memory for RAM and swap. The manual of free defines each column through a field of /proc/meminfo: total is MemTotal; free is MemFree; shared is Shmem; buff/cache is Buffers plus Cached plus SReclaimable; available is MemAvailable, an estimate of how much memory is available for starting new applications without swapping; and used is total minus available (free(1)). MemAvailable exists since Linux 3.14 (proc_meminfo(5)), and the kernel documentation states that it is computed from MemFree, the reclaimable slab, the size of the file lists and the low watermarks, and that it counts the page cache that the system needs to function as not available. The program below recomputes the six columns from /proc/meminfo and compares them with the output of free -k. It reads the file first and calls free second, so the two readings differ by whatever the memory changed between them; the check is the return code, with a tolerance of 64 MiB, and the printed numbers are one sample run.
"""Recompute the columns of `free -k` from /proc/meminfo and compare them with free's output."""
import subprocess
meminfo = {}
with open("/proc/meminfo") as f:
for line in f:
name, rest = line.split(":")
meminfo[name] = int(rest.split()[0]) # every value used here is in kB
mine = {
"total": meminfo["MemTotal"],
"used": meminfo["MemTotal"] - meminfo["MemAvailable"],
"free": meminfo["MemFree"],
"shared": meminfo["Shmem"],
"buff/cache": meminfo["Buffers"] + meminfo["Cached"] + meminfo["SReclaimable"],
"available": meminfo["MemAvailable"],
}
out = subprocess.run(["free", "-k"], capture_output=True, text=True).stdout.splitlines()
theirs = dict(zip(["total", "used", "free", "shared", "buff/cache", "available"],
(int(x) for x in out[1].split()[1:7])))
print(f"{'column':<11}{'from /proc/meminfo':>20}{'from free -k':>14}{'difference':>12} (MiB)")
worst = 0.0
for k in mine:
diff = (mine[k] - theirs[k]) / 1024
worst = max(worst, abs(diff))
print(f"{k:<11}{mine[k] / 1024:20.1f}{theirs[k] / 1024:14.1f}{diff:12.1f}")
print("all columns agree within 64 MiB:", "yes" if worst < 64 else "no")
raise SystemExit(0 if worst < 64 else 1)
column from /proc/meminfo from free -k difference (MiB)
total 15829.2 15829.2 0.0
used 622.1 622.6 -0.5
free 14298.1 14297.6 0.5
shared 3.5 3.5 0.0
buff/cache 1142.6 1142.6 0.0
available 15207.1 15206.6 0.5
all columns agree within 64 MiB: yesIn this sample all six columns agree with free within 0.5 MiB: total, shared and buff/cache agree exactly, and used, free and available differ by 0.5 MiB because the memory changed between the two readings (in other runs the differences were all 0.0, or 1.0 MiB). The identities of the manual hold on this machine.
The definition of used on the lecture's screen is not the one of the free installed here. The slide's top memory line satisfies \(\text{total}=\text{free}+\text{used}+\text{buff/cache}\) exactly, as the previous section computed, so used there is total minus free minus buffers and cache. It does not satisfy \(\text{used}=\text{total}-\text{available}\): the slide's available memory is 2,500,528 KiB, and \(3{,}861{,}052-2{,}500{,}528=1{,}360{,}524\), against the displayed 1,064,472. The version of the lecture's top is not shown, so the chapter does not say which version changed the definition. The consequence for a reader is that the number called used must be read with the manual of the installed version, and that available is the number to use when the question is whether a new process fits.
The other commands of the slide
vmstat reports information about processes, memory, paging, block input and output, traps, disks and processor activity (vmstat(8)). swapon specifies the devices on which paging and swapping take place, and with --show it lists them (swapon(8)); the guest here has 4096 MiB of swap in free, shown in the machine listing. Two entries of the slide need a remark. df is listed with the memory commands, but, as the slide says, it reports disk space: the space used and available on file systems (GNU coreutils manual), which chapter 3 treats. meminfo is not a command: the machine listing shows that no such command exists, and the fields are the file /proc/meminfo, read with cat or grep.
Networking: interfaces, round-trip time and remote login W1L6 2:28
The lecture describes networking in Linux as the configuration, monitoring and management of network connections, protocols and services, and distinguishes two kinds of interface. The loopback interface is a virtual interface for communication within the system, with the default address 127.0.0.1. The physical interfaces are Ethernet (eth0, eth1) and Wi-Fi (wlan0). It then names five commands: ping (test connectivity to a host), ip (show and manipulate routing, devices and policy routing), ssh (secure shell for remote login and command execution), wget (retrieve files from the web) and scp (copy files securely between hosts). It shows one remote login, from a local machine to a cluster, and states that this is the usual way to reach a high-performance system.
Interfaces, and the cost of a message
A host in this section is a machine with a set of network interfaces, each with an IPv4 address of 32 bits written as four decimal bytes. RFC 1122 reserves the addresses whose first byte is 127 as the internal host loopback address and requires that they never appear outside the host (§3.2.1.3, p. 31). The block 127.0.0.0/8 is therefore the loopback address space, and 127.0.0.1 is the one address that the interface lo carries by default; the first output block of the listing below prints lo UNKNOWN 127.0.0.1/8, where the prefix length 8 means that the whole block is local. The WSL guest configures a second address on lo, which the listing does not print because it keeps only the first three fields. The current manual describes ip as showing and manipulating routing, network devices, interfaces and tunnels (ip(8)); the lecture's description names routing, devices and policy routing.
The cost of sending a message of \(m\) bytes between two hosts is modelled in this book as \(T_{\mathrm{msg}}(m)=\alpha+\beta m\), where \(\alpha\) is the latency in seconds and \(\beta\) is the inverse bandwidth in seconds per byte. ping measures a round trip. It sends an ICMP echo request and waits for the echo reply; RFC 792 defines the echo message as type 8 and the reply as type 0, and requires that the data received in the echo message be returned in the reply (pp. 14–15). The default payload is 56 data bytes, which with the 8-byte ICMP header gives the 64 bytes that ping prints (ping(8)). If both directions cost the same, the round-trip time is \(\mathrm{RTT}(m)=2\alpha+2\beta m\). The loopback interface does not use a network card, so \(\alpha\) here is the time of the kernel's software path, and \(\beta^{-1}\) is the rate at which the kernel copies the payload. The listing measures both on this machine and then fetches a file through the interface with wget.
The script prints the loopback interface, then sends 100 echo requests at 10 ms spacing for each of five payload sizes and keeps the minimum round-trip time, which suppresses interference from other processes at the cost of hiding variability. The least-squares line through the five minima gives an intercept and a slope. A second part starts the Python module http.server on a free port of the loopback address, fetches a small file with wget, compares it with the original by cmp, then fetches 200 MB of zeros and divides by the elapsed time. The script starts one server, keeps its PID in $! and ends it with kill on that PID. The printed timings are one sample run; the check is the return code.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
echo "== the loopback interface"
ip -brief address show lo | awk '{print $1, $2, $3}'
echo "== ping on the loopback interface: minimum round-trip time against payload size"
: > rtt.txt
for m in 16 16000 32000 48000 65000; do
ping -c 100 -i 0.01 -s $m -q 127.0.0.1 | awk -F'[/ =]+' -v m=$m '/^rtt/ {print m, $6 * 1000}' >> rtt.txt
done
awk '{printf "payload %6d B minimum RTT %7.1f us\n", $1, $2}' rtt.txt
awk '{n++; sx += $1; sy += $2; sxx += $1 * $1; sxy += $1 * $2}
END {b = (n * sxy - sx * sy) / (n * sxx - sx * sx); a = (sy - b * sx) / n
printf "least squares RTT = %.1f us + %.5f us/B x payload\n", a, b
printf "one way: alpha = %.1f us, 1/beta = %.2f GB/s\n", a / 2, 2 / b / 1000}' rtt.txt
echo "== a file served on the loopback interface and fetched with wget"
head -c 200000000 /dev/zero > big.bin
printf 'iter 500 residual 1.291163e-06\n' > small.log
port=$(python3 -c "import socket; s = socket.socket(); s.bind(('127.0.0.1', 0)); print(s.getsockname()[1])")
python3 -m http.server $port --bind 127.0.0.1 > /dev/null 2>&1 &
server=$!
until wget -q --spider http://127.0.0.1:$port/small.log 2> /dev/null; do sleep 0.1; done
wget -q -O copy.log http://127.0.0.1:$port/small.log
cmp small.log copy.log && echo "copy.log is identical to small.log"
start=$(date +%s.%N)
wget -q -O /dev/null http://127.0.0.1:$port/big.bin
end=$(date +%s.%N)
awk -v t0=$start -v t1=$end 'BEGIN {printf "200 MB over loopback in %.2f s: %.0f MB/s\n", t1 - t0, 200 / (t1 - t0)}'
kill $server
wait $server 2> /dev/null
exit 0
== the loopback interface
lo UNKNOWN 127.0.0.1/8
== ping on the loopback interface: minimum round-trip time against payload size
payload 16 B minimum RTT 26.0 us
payload 16000 B minimum RTT 19.0 us
payload 32000 B minimum RTT 35.0 us
payload 48000 B minimum RTT 38.0 us
payload 65000 B minimum RTT 35.0 us
least squares RTT = 23.3 us + 0.00023 us/B x payload
one way: alpha = 11.6 us, 1/beta = 8.80 GB/s
== a file served on the loopback interface and fetched with wget
copy.log is identical to small.log
200 MB over loopback in 0.10 s: 2060 MB/sThe interface line and the copy check do not vary. In this sample the minimum round-trip time is 26 µs for a 16-byte payload and between 19 and 38 µs for payloads of 16,000 to 65,000 bytes, and the fitted line is \(23.3\ \mu\mathrm{s}+0.00023\ \mu\mathrm{s/B}\cdot m\), so \(\alpha=11.6\ \mu\mathrm{s}\) and \(\beta^{-1}=8.8\) GB/s. In five other runs the intercept was 24.3, 24.3, 26.6, 26.6 and 27.0 µs and the slope 0.0003, 0.0005 and 0.0003 µs/B (three earlier runs, which printed four decimals) and 0.00029 and 0.00018 µs/B (two later runs, five decimals), so \(\alpha\) lies between 11.6 and 13.5 µs and \(\beta^{-1}=2/\text{slope}\) between 4.0 and 11.1 GB/s over the six runs, including the sample's 8.8 GB/s. The slope is not resolved by this method. Each minimum has a resolution of 1 µs, the five minima do not increase monotonically (in this sample the minimum at 16,000 B, 19 µs, is below the one at 16 B, 26 µs), and the slope is the difference of numbers of that resolution. The measurement determines \(\alpha\) to within about 15 % and \(\beta\) only to within a factor of 2.8. The file transfer gives a second bound: 200 MB in 0.10 s is 2.06 GB/s in this sample (2.1 to 2.3 GB/s in three other runs on an otherwise idle machine; in a run made while other processes were active it fell to 1.07 GB/s, with \(\alpha=10.1\ \mu\mathrm{s}\) and \(\beta^{-1}=4.45\) GB/s), which is a lower bound on the rate of the loopback path, because the figure includes the Python server and wget, and it depends on the load. With \(\alpha=12\ \mu\mathrm{s}\) and a bandwidth between 1.1 and 11.1 GB/s, the message size at which the latency equals the transfer time, \(m_{1/2}=\alpha/\beta\), lies between 13 kB and 133 kB. The numbers describe the software path inside one machine. They say nothing about a physical network, whose latency and bandwidth depend on the cable, the card and the switch, and which chapters 14 and 28 measure with MPI.
Remote login and copying
The lecture's ssh example logs in from a local machine to a server with the command ssh user@address; the server asks for a password, and after it accepts, the prompt shows that the commands now run on the server and the directory listing is that of the server. RFC 4251 describes the protocol as three components: the transport layer protocol provides server authentication, confidentiality and integrity; the user authentication protocol authenticates the client to the server; and the connection protocol multiplexes the encrypted tunnel into logical channels (§1). The ssh manual describes the program as one for logging into a remote machine and for executing commands on it (ssh(1)); with a command after the host name it runs that command and returns its output without an interactive login. The test machine has no SSH server, so the chapter does not demonstrate a login. The option -G makes ssh print the configuration that it would use for a connection and exit, which lets a person check the user, the host and the port that a command line selects before connecting.
The lecture states that scp copies files securely between hosts. The manual states that scp uses the SFTP protocol over an ssh connection and the same authentication and security as a login session (scp(1)). That was not always so: the OpenSSH 9.0 release notes (April 2022) record the switch of scp from the legacy scp/rcp protocol to SFTP by default, and note that the legacy protocol expanded wildcards in remote file names through the remote shell, which made double quoting of shell characters necessary. The machine here has OpenSSH 9.6, so the new behaviour applies. The script below uses only commands that need no server. ssh -G shows the connection that a command line selects, scp between two local paths shows that the command line is the same as for a remote copy, and a name with a colon shows the rule by which scp reads the text before a colon as a host name. The output is deterministic, and the check is exact.
cd "$(mktemp -d /tmp/hpsc-demo.XXXXXX)"
echo "== the connection ssh would make, without making it"
ssh -G -p 2222 alice@login.example.org 2> /dev/null | grep -E '^(user|hostname|port) '
echo "== scp between two local paths uses the same command line as a remote copy"
printf 'iter 500 residual 1.291163e-06\n' > run.log
scp run.log run_copy.log && cmp run.log run_copy.log && echo "run_copy.log is identical to run.log"
echo "== a colon in the first path makes scp read a host name"
echo data > a:b.log
scp a:b.log . > /dev/null 2>&1; echo "scp a:b.log . exit status: $? (the host a could not be reached)"
scp ./a:b.log c.log && echo "./a:b.log is read as a local path"
== the connection ssh would make, without making it
user alice
hostname login.example.org
port 2222
== scp between two local paths uses the same command line as a remote copy
run_copy.log is identical to run.log
== a colon in the first path makes scp read a host name
scp a:b.log . exit status: 255 (the host a could not be reached)
./a:b.log is read as a local pathThe command line ssh -p 2222 alice@login.example.org selects the user alice, the host login.example.org and port 2222, as -G prints. The local copy produces an identical file. A file name with a colon, a:b.log, is read as the file b.log on a host named a; the attempt fails with status 255 because the host cannot be reached, and the path ./a:b.log is read as a local file. The practical rule for a log or result with a colon in its name, for example a timestamp, is to give the path a leading ./. The chapter did not test password or key authentication, host-key checking or wget against a remote server; the lecture's example uses a password, and a cluster's access policy decides whether keys are required.
What the chapter establishes and what it does not
The table lists the statements of the lectures that this chapter tested, with the status that the tests gave them. Where a spoken statement and a slide differ, the table says which one is tested.
| Statement of the lecture | Status | Evidence in this chapter |
|---|---|---|
The lecture describes sleep as putting the CPU into an idle state. | Refined | The process blocks in state S and uses no processor time; the processor is idle only if nothing else is runnable (jobs_demo.sh, states.c). |
| A process is put into the sleeping state because a higher-priority process arrives (spoken). | Not supported; the slide is correct | A preempted process stays in R; two busy loops on one processor are both R. Sleeping means waiting for an event (states.c; ps(1)). |
| A zombie is a finished process whose memory has not been cleaned (spoken). | Corrected; the slide is correct | A zombie has no VmRSS line; the kernel keeps PID, status and resource usage in a process-table slot, which is kernel bookkeeping and no user memory (states.c; wait(2)). |
The lecture presents ps -e as listing all processes, including killed, stopped and zombie ones. | Refined | It lists every existing process, including stopped and zombie ones; a killed process that its parent has waited for no longer exists. |
The numbers of the top screen. | Consistent | \(1+206=207\) tasks; the processor line sums to 100.0; total \(=\) free \(+\) used \(+\) buff/cache; \(183{,}760/3{,}861{,}052=4.76\,\%\) is the printed 4.8. |
kill sends SIGTERM by default; SIGKILL terminates by force; SIGSTOP stops and SIGCONT resumes. | Confirmed | Numbers 15, 9, 19 and 18 on x86 and ARM; SIGKILL and SIGSTOP cannot be caught (states.c; signal(7), kill(1)). |
| In an HPC run each process, or each thread, works on one core. | Refined | The affinity mask defaults to all processors and is narrowed only by a call such as sched_setaffinity (states.c; sched_setaffinity(2)). |
grep -r "Ved" * searches the files and directories below the current one. | Refined | The shell expands * without names that begin with a dot; grep -r Ved . reads all (pipes.sh, section 8). |
awk '/M/ {print $0}' selects the males. | True for the sample file only | The pattern matches any line that contains M; $3 == "M" compares the field (lecture_files.sh). |
sort sorts numerically. | Refined | -n ignores exponents; -g reads them (pipes.sh, section 4). |
uniq filters duplicate lines from sorted input. | Confirmed | Only adjacent duplicates are removed (pipes.sh, section 3). |
| The pipe passes the output of one command as input to another. | Confirmed for standard output; incomplete | The stages run at the same time, the capacity is 65,536 bytes, a closed reader raises SIGPIPE, standard error is not carried (pipes.sh, sections 1, 2, 10). |
wc file2 prints 4 11 61. | Lines and words confirmed; bytes unresolved | The four lines as displayed have 60 bytes; the extra byte of the slide is not visible (lecture_files.sh). |
The memory slide lists df and meminfo as commands. | Placement of df refined; meminfo corrected | df reports file-system space, as the slide says; meminfo is the file /proc/meminfo (machine.sh). |
free shows RAM and swap usage. | Confirmed, with a version note | Columns equal their /proc/meminfo definitions; the used of the lecture's screen is total \(-\) free \(-\) buff/cache, not total \(-\) available (meminfo_check.py). |
| The loopback interface has the default address 127.0.0.1. | Refined | The interface carries 127.0.0.1/8, and the whole block is loopback (RFC 1122 §3.2.1.3). |
ssh gives remote login and command execution; scp copies securely. | Confirmed | ssh(1), scp(1); since OpenSSH 9.0 scp uses SFTP by default (release notes). |
The chapter establishes the following. The formal model of streams, filters and pipelines describes which bytes flow, and the semantics of the pipe adds concurrency, a bounded buffer, exit statuses and a signal that the model omits. A regular expression defines a language, grep selects the lines that contain a string of that language, and a derivative matcher agrees with grep -E on the 127 shortest strings for seven expressions. A residual log of the Jacobi iteration has a factor per sweep that tends to \(\cos(\pi/(N+1))\), the factor from the last interval equals \(\rho\) to the six printed digits for \(N=16\) and 32 and agrees to \(2\times10^{-7}\) in relative terms for \(N=8\), and the end of the run is predicted to within one sweep from the last logged line, and from \(N\) alone to within 0.7 % for \(N\le500\) and 26.5 % low for \(N=1000\), where the stopping time precedes the end of the transient. The resident size of an anonymous allocation equals the predicted size after the first write. The columns of free are the stated combinations of /proc/meminfo fields.
The chapter leaves out the following. The derivative matcher covers an ERE subset and strings of length at most 6 over two letters; it is not a proof for grep. Thompson's 1968 paper and Brzozowski's 1964 paper were not opened, so the history of the constructions rests on Cox (2007) and on Owens, Reppy and Turon (2009). Locales other than C were not tested, because the machine has none. The interactive commands fg, top and a remote ssh login were not run; their description rests on the lecture's slides and on the manuals. The timing measurements (the backtracking times, the ping minima and the file transfer rate) are single sessions on one laptop under WSL 2 with the run-to-run spread stated beside each; the ping slope in particular is not resolved. The closed form for the convergence factor is specific to Jacobi on a square grid with Dirichlet edges. The memory model covers one anonymous allocation and does not cover shared pages, file-backed pages, memory limits set by a container or a scheduler, or non-uniform memory. Each listing whose check is exact was run twice in the code lab and printed the same output both times; that is evidence of determinism and not of correctness beyond the stated checks.
Exercises
Exercise 1 (derive). Let \(k_{10}\) be the number of sweeps in which the residual of the Jacobi iteration falls by a factor of 10 in the asymptotic range. Express \(k_{10}\) through (4.4), show that \(k_{10}\approx2(N+1)^{2}\ln10/\pi^{2}\) with a relative error of about \(\theta^{2}/6\) where \(\theta=\pi/(N+1)\), and evaluate both forms for \(N=16\) and \(N=1000\). Compare the exact value for \(N=16\) with the number of sweeps per decade that the log of the first listing shows between sweep 100 and sweep 400.
Solution
In the asymptotic range \(r_{k+k_{10}}=\rho^{k_{10}}r_k\), so \(\rho^{k_{10}}=1/10\) and \(k_{10}=\ln10/(-\ln\rho)\) with \(\rho=\cos\theta\). The series \(-\ln\cos\theta=\theta^{2}/2+\theta^{4}/12+\cdots\) gives \(-\ln\rho=(\theta^{2}/2)(1+\theta^{2}/6+\cdots)\), so \(k_{10}=(2\ln10/\theta^{2})(1-\theta^{2}/6+\cdots)\), and the leading term \(2(N+1)^{2}\ln10/\pi^{2}\) overestimates by the relative amount \(\theta^{2}/6\). For \(N=16\), \(\theta=0.18480\), \(\theta^{2}/6=0.0057\); the exact value is \(134.08\) sweeps and the approximation is \(134.85\), 0.57 % higher. For \(N=1000\), \(\theta^{2}/6=1.6\times10^{-6}\), the exact value is \(467{,}534.2\) sweeps and the approximation is \(467{,}535.0\). The log of the first listing has \(r_{100}=1.296030\times10^{-3}\) and \(r_{400}=7.191545\times10^{-6}\), a ratio of 180.2 over 300 sweeps, which is \(300/\log_{10}180.2=133.0\) sweeps per decade, 0.8 % below the exact 134.08 because the window starts in the transient, as the window estimate of the section on convergence did.
Exercise 2 (compute). A machine reports MemTotal 16,209,100 kB, MemFree 15,273,520 kB, MemAvailable 15,599,304 kB, Buffers 58,052 kB, Cached 442,656 kB, SReclaimable 29,796 kB and Shmem 3,540 kB. (a) Compute the used, free, buff/cache and available columns of free -m as the current manual defines them. (b) Does the pair of grids of the running case fit for \(N=20000\)? (c) What is the largest \(N\) whose two grids fit in the 2,500,528 KiB that the lecture's top screen reports as available?
Solution
(a) Dividing by 1024 gives mebibytes. used \(=16{,}209{,}100-15{,}599{,}304=609{,}796\) kB \(=595.5\) MiB. free \(=15{,}273{,}520\) kB \(=14{,}915.5\) MiB. buff/cache \(=58{,}052+442{,}656+29{,}796=530{,}504\) kB \(=518.1\) MiB. available \(=15{,}599{,}304\) kB \(=15{,}233.7\) MiB. (These are the readings of the machine of this chapter at one instant.) (b) Two grids need \(16\times20002^{2}=6{,}401{,}280{,}064\) bytes \(=5.96\) GiB, and 15,233.7 MiB is 14.88 GiB, so the grids fit with a factor of 2.5 to spare; a fifth grid of 2.98 GiB, or a program that holds more than 8.9 GiB elsewhere, would change the answer. (c) The available memory is \(2{,}500{,}528\times1024=2{,}560{,}540{,}672\) bytes. Dividing by 16 gives \(160{,}033{,}792\), whose square root is \(12{,}650.4\), so \((N+2)\le12{,}650\) and \(N\le12{,}648\). The grids of \(N=20000\) do not fit there, since 5.96 GiB exceeds the 2.38 GiB available.
Exercise 3 (counterexample). A script finds the smallest residual of a log with grep '^iter' solver.log | awk '{print $4}' | sort -n | head -n 1 and counts the distinct residual values with uniq | wc -l. Give a three-line input on which the first command returns the largest residual and a three-line input on which the second reports 3 for a file with two distinct lines.
Solution
For the first command take the residual column 1.2e-03, 9.5e-05, 4.0e-05. sort -n reads only the leading numeric strings 1.2, 9.5 and 4.0, because it does not recognize the exponent (GNU coreutils manual), orders them as 1.2, 4.0, 9.5, and head -n 1 returns 1.2e-03, the largest value. The listing of the pipeline section shows the same effect for four values. The command that gives the right answer is sort -g | head -n 1, which returns 4.0e-05. For the second command take the lines 1e-3, 5e-4, 1e-3. uniq removes only adjacent repeats, the two equal lines are not adjacent, and uniq | wc -l prints 3 for two distinct lines. The right commands are sort -u | wc -l or sort | uniq | wc -l, which print 2.
Exercise 4 (diagnose an assumption). A script contains grep '^iter' missing.log | tail -n 1 | awk '{print $4}' followed by if [ $? -eq 0 ]; then echo "last residual read"; fi. The file missing.log does not exist. State what the script prints, name the false assumption and give two repairs. Then say what a script sees if it sets set -o pipefail and ends a pipeline that reads a large input with head.
Solution
The script prints last residual read. The grep fails with status 2 and a message on standard error (the file does not exist), tail and awk succeed on empty input, and the status of the pipeline is the status of the last command, 0 (POSIX.1-2017, Shell Command Language §2.9.2). The false assumption is that the status of a pipeline reports the failure of any stage. In Bash, echo "${PIPESTATUS[@]}" directly after the pipeline prints 2 0 0 for this case. The first repair is set -o pipefail, under which the status is the status of the rightmost failing command, here 2. The second repair is to test the input first, with [ -r missing.log ] or with the status of grep in a separate command. With pipefail a pipeline that ends in head and reads more than head consumes (the first section of pipes.sh) reports 141, the status of a seq killed by SIGPIPE, although every line that head printed was correct. A script that enables pipefail must therefore either avoid head at the end of a long pipeline or accept 141 as success for that stage.
Exercise 5 (design judgment). A run with \(N=1000\) that must bring the error below \(10^{-6}\) needs about 2.6 million sweeps, which is 2.4 hours at the 3.3 ms per sweep measured in this chapter. The only machine available is a shared login node. Choose among starting the solver with a plain &, starting it with nohup, starting it in a terminal multiplexer, and submitting it to the batch scheduler. Give the quantitative facts of this chapter that bear on the choice, and say what to log and at what interval.
Solution
A plain & is the worst choice: when the terminal closes, SIGHUP terminates the job, and wait would report status 129 (jobs_demo.sh). nohup survives the hangup and writes to nohup.out if the output is not redirected, so, after changing max_iter to at least 2,700,000 and tol to \(4.9\times10^{-12}\) in the source (neither is a command-line argument), the command should be nohup ./jacobi_log 1000 1000 > run.log 2> run.err & with the PID kept from $! for later ps and kill commands. A terminal multiplexer keeps the session alive in the same way and adds the ability to reattach; the chapter did not test one. The batch scheduler is the correct choice on a shared node: the run holds one processor for hours, and the lecture's own motivation for top is the load that a process puts on a shared system; chapter 30 treats the scheduler. The memory is not a constraint, since two grids need 15.3 MiB. The stopping rule needs a change: the solver of the first listing stops at \(r\lt10^{-6}\), which for \(N=1000\) ends the run after 191,001 sweeps with an error of 0.167; for an error below \(10^{-6}\) the tolerance must be about \(10^{-6}(1-\rho)=4.9\times10^{-12}\) by (4.8) (\(3.4\times10^{-12}\) for a guaranteed max-norm bound, which needs the factor 1.45). The log size follows from the interval: with a line every 1000 sweeps the log has about 2600 lines; with a line every 50 sweeps it has 52,000 lines of about 35 bytes, about 1.8 MB. A line every 1000 sweeps is enough to estimate the factor from the last two lines with (4.4) and to predict the end with (4.6), provided that the run is past the transient. The transient does not shorten for a large grid: the ratio of the second eigenvalue \(\mu_{21}\) to \(\rho\) is about \(1-3\theta^{2}/4\), so the transient lasts a number of sweeps that grows as \(N^{2}\), like the run itself. A residual line with the iteration number, written with fflush or to a file, lets tail -n 2 and one awk program report the state of the run at any time.
Exercise 6 (implementation and measurement). Write an awk program that reads a log of the format of the first listing and prints \(\hat\rho_{\mathrm{last}}\), \(\rho\), the end predicted by (4.6) from the last progress line, the end predicted from the first progress line, and the sweep at which the run converged. Run the solver with ./jacobi_log 64 500 and apply the program. State how far each prediction is from the observed end.
Solution
The program reads \(N\) and the tolerance from the header, keeps the first and the last two progress lines, and reads the final sweep from the last line of the log:
awk '/^# jacobi/ { split($3, a, "="); N = a[2]; split($4, b, "="); tol = b[2] }
/^iter/ { if (!n++) { k0 = $2; r0 = $4 } kp = k1; rp = r1; k1 = $2; r1 = $4 }
/^# converged/ { split($3, a, "="); kc = a[2] }
END { rho = cos(atan2(0, -1) / (N + 1)); rhat = (r1 / rp) ^ (1 / (k1 - kp))
printf "rho_hat_last=%.6f rho=%.6f predicted=%.1f from_first=%.1f converged=%d\n", rhat, rho,
k1 + log(tol / r1) / log(rhat), k0 + log(tol / r0) / log(rho), kc }' solver.logThe solver with \(N=64\) and a line every 500 sweeps writes ten progress lines and converges at sweep 5272 with residual \(9.997952\times10^{-7}\). The program prints rho_hat_last=0.998832 rho=0.998832 predicted=5271.8 from_first=5719.4 converged=5272. The factor from the last two lines equals \(\rho\) to the six printed digits. The prediction from the last progress line (sweep 5000, \(r=1.373855\times10^{-6}\)), using \(\hat\rho_{\mathrm{last}}\) in place of \(\rho\) in (4.6), is 5271.8, 0.2 sweeps below the observed end. The prediction from the first line (sweep 500, \(r=4.452550\times10^{-4}\)), using \(\rho\), is 5719.4, which is 447 sweeps or 8.5 % above the observed end: the early residual lies above the asymptote \(A\rho^{k}\), and extrapolating from it with the asymptotic factor overestimates the remaining work. The overestimate is 3.4 % for \(N=16\) (first line at sweep 50) and 9.1 % for \(N=32\) (first line at sweep 100), so it does not fall as the grid is refined (3.4 %, 9.1 % and 8.5 % for \(N=16,32,64\)); it depends on how early in the run the first line lies. The numbers of this solution come from running the solver and the program on this machine in a separate session; the code lab does not run exercise solutions.
Primary sources
- Recordings: W1L5, Mastering Linux Text Processing and File Management (slides: process attributes, background and foreground, states,
ps,top,kill, multitasking,grep,awk,sort,uniq, pipe,wc,head,tail,diff,paste,tr); W1L6, Linux Memory and Networking Commands (slides: memory concepts,free,vmstat,df,swapon,meminfo, loopback and physical interfaces,ping,ip,ssh,wget,scp), NPTEL High Performance Scientific Computing, IIT Bombay, 2025. - The Open Group, POSIX.1-2017 Base Definitions, §9 Regular Expressions. §9.1: the leftmost-longest matching rule; §9.3.5: range expressions are specified only in the POSIX locale; §9.3 and §9.4: BRE and ERE, back-references in BRE; §9.5.3: ERE grammar. Base Definitions §3.206: definition of a line.
- The Open Group, POSIX.1-2017 Shell Command Language, §2.8.2, §2.9.2 and §2.9.3 (and POSIX.1-2024 §2.9.2, which adds the
pipefailoption and its exit-status rule): §2.8.2, the exit status of a command that a signal terminated is greater than 128; §2.9.2 and §2.9.3, the pipe "as if by creating a pipe", the exit status of the last command, the shell may also wait for all commands; asynchronous lists, standard input from/dev/nullwhen job control is disabled,$!. - The Open Group, POSIX.1-2017 utilities
awk(arithmetic follows ISO C floating point; comparison of numeric strings),sort(-n: initial numeric string),uniqandgrep. - Free Software Foundation, GNU grep manual: §2.1.6 (
-rand the working directory), §2.3 (exit status 0, 1, 2), §3.5 (back-references), §3.6 (BRE against ERE). GNU awk manual: chapter 1 (pattern–action rules), §4.5.1 (default field splitting), §7.1.4 (BEGINandEND). GNU coreutils manual:sort(-ndoes not recognize exponents;-gconverts a prefix to floating point),uniq(only adjacent repeats;sort -u),nohup(hangup ignored;nohup.out),df(file-system space). - S. Owens, J. Reppy and A. Turon, "Regular-expression derivatives re-examined", Journal of Functional Programming 19(2) (2009) 173–190 (bibliographic data checked in Crossref). Definitions 2.1 and 2.2 (syntax and language), §3.1 (the derivative rules, due to Brzozowski), §3.2 (matching by derivatives). Used for (4.1) and (4.2). The original, J. A. Brzozowski, "Derivatives of regular expressions", Journal of the ACM 11(4) (1964) 481–494, was not opened; its bibliographic data were checked in Crossref.
- R. Cox, "Regular Expression Matching Can Be Simple And Fast" (January 2007): backtracking against automata on \(a?^{n}a^{n}\); the Thompson NFA simulation runs in \(O(|r|\,n)\); GNU grep and GNU awk build DFAs; back-references are not regular and need exponential search in the worst case; Thompson's 1968 paper (CACM 11(6) 419–422) is described there. The paper itself could not be opened (the publisher's page returned a bot-check page); the volume, issue and pages were checked in Crossref.
- M. Kerrisk et al., Linux man-pages: ps(1) (default selection;
-e,-f; process state codes D, I, R, S, T, t, W, X, Z), top(1) (%CPU,%MEM), kill(1) (default SIGTERM), signal(7) (SIGKILL and SIGSTOP cannot be caught; signal numbers by architecture; SIGTTIN, SIGPIPE, SIGHUP), wait(2) (zombies, NOTES), pipe(7) (SIGPIPE; capacity 65,536 bytes), sched_setaffinity(2), proc_pid_stat(5) (state field), proc_pid_status(5) (VmSize,VmRSS; inaccurate values), proc_pid_statm(5) (smapsandsmaps_rollupfor accurate values), clone(2) (CLONE_THREAD), proc_meminfo(5) (MemAvailable), free(1) (the columns and their/proc/meminfofields), vmstat(8), swapon(8), ip(8), ping(8) (default payload 56 bytes, 64 ICMP bytes), ssh(1) (-G), scp(1) (SFTP over ssh). - The Linux kernel documentation, The
/procfilesystem:MemAvailableis an estimate of the memory available for starting new applications without swapping, computed fromMemFree,SReclaimable, the file LRU lists and the low watermarks. - R. Braden (ed.), RFC 1122, Requirements for Internet Hosts – Communication Layers (1989), §3.2.1.3: addresses {127, any} are the internal host loopback address and must not appear outside a host. J. Postel, RFC 792, Internet Control Message Protocol (1981), p. 14: echo is type 8, echo reply type 0, and the data received in the echo message must be returned in the reply. T. Ylonen and C. Lonvick, RFC 4251, The Secure Shell (SSH) Protocol Architecture (2006), §1: transport layer, user authentication and connection protocols.
- The Open Group, POSIX.1-2017 Base Definitions §11.1.10 (Modem Disconnect): SIGHUP is sent to the controlling process of the terminal. Free Software Foundation, GNU Bash manual, "Signals" (an interactive shell resends SIGHUP to all jobs, running or stopped) and "Exit Status" (a command killed by a fatal signal with number N has the status 128+N).
- OpenSSH, release notes of version 9.0:
scpswitches from the legacy scp/rcp protocol to the SFTP protocol by default; the legacy protocol expanded remote wildcards through the remote shell. - J. Demmel, CS267 notes for lectures 15 and 16 (5 and 7 March 1996), Solving the Discrete Poisson Equation using Jacobi, SOR, Conjugate Gradients, and the FFT, Jacobi's method: the iteration, the error reduction factor \(\rho_{\mathrm{Jacobi}}(n)=\cos(\pi/(n+1))\), its approximation \(1-\tfrac12(\pi/(n+1))^{2}\), and \(\rho_{\mathrm{Gauss\text{-}Seidel}}=\rho_{\mathrm{Jacobi}}^{2}\).