2024S

Problem 1

Given an integer $k>0$, we define a language $L_k$ over an alphabet $\Sigma =\{a,b\}$ by:

$$L_k=\{x_1\dots x_n\in {\Sigma }^{\ast }\mid n\in \mathbb{Z}\wedge n\ge k\wedge x_{n-k+1}=a\}$$

Here, $\mathbb{Z}$ is the set of integers and $x_i\in \Sigma$. That is, $L_k$ is the language that consists of words whose $k$-th symbol from the last is $a$.

Answer the following questions.

1. Give a non-deterministic finite automaton that accepts $L_3$.

2. Describe $L_k$ using a regular expression. You may write the $i$-time concatenation of a regular expression $r$ as $r^i$.

3. Is $L^{\prime }={\bigcup }_{k=1}^{\infty }{L}_{k^2}$ a regular language? If so, give a finite automaton that accepts $L^{\prime }$. If not, prove that $L^{\prime }$ is not regular. You may use the pumping lemma for regular languages.

4. Prove that any deterministic finite automaton that accepts $L_k$ has at least $2^k$ states.

---

给定一个整数 $k>0$，我们通过以下方式定义了一个字母表 $\Sigma =\{a,b\}$ 上的语言 $L_k$：

$$L_k=\{x_1\dots x_n\in {\Sigma }^{\ast }\mid n\in \mathbb{Z}\wedge n\ge k\wedge x_{n-k+1}=a\}$$

这里，$\mathbb{Z}$ 是整数集，并且 $x_i\in \Sigma$。也就是说，$L_k$ 是由那些倒数第 $k$ 个符号是 $a$ 的单词组成的语言。

回答以下问题。

1. 给出一个接受 $L_3$ 的非确定性有限自动机。

2. 使用正则表达式描述 $L_k$。你可以将正则表达式 $r$ 的 $i$ 次连接写为 $r^i$。

3. $L^{\prime }={\bigcup }_{k=1}^{\infty }{L}_{k^2}$ 是正则语言吗？如果是，给出一个接受 $L^{\prime }$ 的有限自动机。如果不是，证明 $L^{\prime }$ 不是正则的。你可以使用正则语言的抽水引理。

4. 证明任何接受 $L_k$ 的确定性有限自动机至少有 $2^k$ 个状态。

---

Problem 2

Consider a processor $P$ with a direct-mapped data cache that stores 256 bytes of data in total. The cache line size (block size) of the data cache is 16 bytes. Through the data cache, the processor $P$ reads data from the memory by the load-word instruction lw and writes data to the memory by the store-word instruction sw. The address and data bit-widths of the load-word/store-word instructions are 32. When the bit representation of a memory address is $a_{31}{a}_{30}\dots a_0$, the index and the offset of the data cache are $a_7{a}_6{a}_5{a}_4$ and $a_3{a}_2{a}_1{a}_0$, respectively. The processor $P$ has 32 integer registers from x0 to x31, and x0 is the zero register that always keeps the value 0.

The following program $S$ applies the average filter with size 3 to the one-dimensional array $A$ with head address 0x1000 and size 402 and stores the result on the one-dimensional array $B$ with head address 0x2000 and size 400. Each element of the arrays $A$ and $B$ is a 32-bit signed integer. The behavior of each instruction is described as a comment (the description after #) in the program, where memory[addr] represents a memory access to the address addr. The initial values of the registers x5, x6, and x7 are 0x1640, 0x1000, and 0x2000, respectively.

Instruction  0)    addi x2, x0, 3     # x2 <- x0 + 3
Instruction  1)    Loop: lw x3, 0(x6)  # x3 <- memory[x6 + 0]
Instruction  2)    lw x9, 4(x6)        # x9 <- memory[x6 + 4]
Instruction  3)    add x8, x8, x9      # x8 <- x8 + x9
Instruction  4)    lw x9, 8(x6)        # x9 <- memory[x6 + 8]
Instruction  5)    add x8, x8, x9      # x8 <- x8 + x9
Instruction  6)    div x8, x8, x2      # x8 <- x8 / x2
Instruction  7)    sw x8, 0(x7)        # memory[x7 + 0] <- x8
Instruction  8)    addi x6, x6, 4      # x6 <- x6 + 4
Instruction  9)    addi x7, x7, 4      # x7 <- x7 + 4
Instruction 10)    blt x6, x5, Loop    # if x6 < x5, goto Loop

Answer the following questions:

1. Calculate the cache hit rate up to three places of decimals for the execution of the program $S$ on the processor $P$. Suppose that every cache line of the data cache is invalid when the execution of the program starts, and there is no prefetcher.

2. Calculate the IPC (instructions per cycle) up to three places of decimals for the execution of the program $S$ on the processor $P$. Suppose that the processor $P$ has an instruction memory with no access delay, and there is no delay on the instruction fetch, instruction decode, data forwarding, and write-back to the register file. The processor starts at most one instruction execution for every clock cycle. Until the instruction completes, the processor does not start the subsequent instructions. The processor executes each of add, addi, and blt instructions in one clock cycle, and executes div instruction in four clock cycles. The processor executes each of lw and sw instructions in one clock cycle in case of cache hits and four clock cycles in case of cache misses.

3. Consider a modification to the data cache to improve the cache hit rate for the execution of the program $S$. Explain the modification with the reason why the cache hit rate is improved. Note that the data cache capacity should not be modified.

4. Explain a software-level optimization of the program $S$, using a concrete example, for improving the cache hit rate without any modification to the processor $P$ or the data cache.

---

考虑一个处理器 $P$，它有一个直接映射的数据缓存，总共存储 256 字节的数据。数据缓存的缓存行大小（块大小）为 16 字节。通过数据缓存，处理器 $P$ 通过加载字指令 lw 从内存读取数据，并通过存储字指令 sw 将数据写入内存。加载字/存储字指令的地址和数据位宽为 32。当一个内存地址的位表示为 $a_{31}{a}_{30}\dots a_0$ 时，数据缓存的索引和偏移量分别为 $a_7{a}_6{a}_5{a}_4$ 和 $a_3{a}_2{a}_1{a}_0$。处理器 $P$ 有 32 个整数寄存器，从 $x0$ 到 $x31$，其中 $x0$ 是始终保持值 0 的零寄存器。

下面的程序 $S$ 将大小为 3 的均值滤波应用于一维数组 $A$（头地址为 0x1000，大小为 402），并将结果存储在一维数组 $B$（头地址为 0x2000，大小为 400）上。数组 $A$ 和 $B$ 的每个元素都是 32 位有符号整数。每条指令的行为在程序中的注释（# 之后的描述）中描述，其中 $\mathrm{memory}[\mathrm{addr}]$ 表示对地址 $\mathrm{addr}$ 的内存访问。寄存器 $x5$、$x6$ 和 $x7$ 的初始值分别为 0x1640、0x1000 和 0x2000。

指令  0)    addi x2, x0, 3     # x2 <- x0 + 3
指令  1)    Loop: lw x3, 0(x6)  # x3 <- memory[x6 + 0]
指令  2)    lw x9, 4(x6)        # x9 <- memory[x6 + 4]
指令  3)    add x8, x8, x9      # x8 <- x8 + x9
指令  4)    lw x9, 8(x6)        # x9 <- memory[x6 + 8]
指令  5)    add x8, x8, x9      # x8 <- x8 + x9
指令  6)    div x8, x8, x2      # x8 <- x8 / x2
指令  7)    sw x8, 0(x7)        # memory[x7 + 0] <- x8
指令  8)    addi x6, x6, 4      # x6 <- x6 + 4
指令  9)    addi x7, x7, 4      # x7 <- x7 + 4
指令 10)    blt x6, x5, Loop    # if x6 < x5, goto Loop

回答以下问题：

1. 计算程序 $S$ 在处理器 $P$ 上执行的缓存命中率，保留到小数点后三位。假设当程序执行开始时，数据缓存的每一行都是无效的，并且没有预取器。

2. 计算程序 $S$ 在处理器 $P$ 上执行的 IPC（每周期指令数），保留到小数点后三位。假设处理器 $P$ 具有无访问延迟的指令存储器，并且指令提取、指令解码、数据转发和寄存器文件的写回没有延迟。处理器最多在每个时钟周期启动一条指令的执行。在指令完成之前，处理器不会启动后续指令。处理器在一个时钟周期内执行每条 add、addi 和 blt 指令，并在四个时钟周期内执行 div 指令。处理器在缓存命中情况下在一个时钟周期内执行每条 lw 和 sw 指令，而在缓存未命中情况下在四个时钟周期内执行。

3. 考虑对数据缓存进行修改以提高程序 $S$ 执行的缓存命中率。解释修改的内容以及缓存命中率提高的原因。注意数据缓存容量不应修改。

4. 解释程序 $S$ 的一种软件级优化，使用一个具体的例子，在不对处理器 $P$ 或数据缓存进行任何修改的情况下提高缓存命中率。

---

Problem 3

Let $G=(V,E)$ be an undirected graph with no self-loops (edges joining the same vertex) nor multi-edges (two or more edges joining the same two vertices), with $|V|=n$, $|E|=m$. If there is a vertex $v$ in a connected graph $G$ such that after deleting $v$, the resulting graph is not connected, we call $v$ a cut vertex of $G$.

Answer the following questions:

1. Describe an algorithm to check whether or not $G$ is connected. Estimate the time complexity of the algorithm.

2. Describe a $O(m)$ time algorithm to find a spanning tree $T$, given a connected graph $G$.

3. Let $T$ be a spanning tree of a connected graph $G$, and assume that $v$ is a non-leaf node of $T$ (i.e., the degree of $v$ in $T$ is at least two) and that $v$ is not a cut vertex of $G$. Let $e$ be an edge of $T$ that is incident with $v$. Prove that one can obtain another spanning tree of $G$ from $T$ by replacing $e$ with another edge $f\ne e$ of $G$.

4. Describe a $o(mn)$ time algorithm, given a connected graph $G$, to find all cut vertices of $G$.

---

设 $G=(V,E)$ 为一个无向图，该图没有自环（连接到同一顶点的边）也没有重边（连接同一对顶点的两个或更多边），且 $|V|=n$，$|E|=m$。如果在一个连通图 $G$ 中有一个顶点 $v$，使得删除 $v$ 后所得的图不再连通，我们称 $v$ 为 $G$ 的割点。

回答以下问题：

1. 描述一个算法来检查 $G$ 是否连通。估计该算法的时间复杂度。

2. 描述一个 $O(m)$ 时间的算法，给定一个连通图 $G$，找到一棵生成树 $T$。

3. 设 $T$ 为连通图 $G$ 的一棵生成树，并假设 $v$ 是 $T$ 的一个非叶节点（即 $v$ 在 $T$ 中的度数至少为二），并且 $v$ 不是 $G$ 的割点。令 $e$ 为 $T$ 中与 $v$ 相邻的一条边。证明通过用 $G$ 的另一条边 $f\ne e$ 替换 $e$，可以得到 $G$ 的另一棵生成树。

4. 描述一个 $o(mn)$ 时间的算法，给定一个连通图 $G$，找到 $G$ 的所有割点。

---

Problem 4

Let us consider the following function $f$ described in a C-like programming language with the call-by-value evaluation strategy. We assume that, unlike in the C language, there is no bound on integer data, and no overflow occurs.

int f(int x)
{
    if (x <= 0) return x + 1;
    else return f(f(x - 2));
}

For example, $f(1)$ is evaluated as follows, where the return value is 1 and the number of calls of the function $f$ during the evaluation is 3.

$$f(1)\to f(f(-1))\to f(0)\to 1.$$

Answer the following questions:

1. Give the number of calls of the function $f$ during the evaluation of $f(2)$.

2. Show that the return value of $f(n)$ is 1 for every non-negative integer $n$.

3. Let $n$ be a non-negative integer. Express the number of calls of the function $f$ during the evaluation of $f(n)$ in terms of $n$.

4. Let $n$ be a non-negative integer. Express the number of calls of the function $f$ when $f(n)$ is evaluated by using the call-by-name strategy instead of the call-by-value strategy, in terms of $n$.

5. Give an example of a program that does not terminate with the call-by-value strategy but terminates with the call-by-name strategy.

---

让我们考虑以下在类似 C 的编程语言中描述的函数 $f$，该语言采用值传递（call-by-value）求值策略。我们假设，与 C 语言不同，整数数据没有限制，也不会发生溢出。

int f(int x)
{
    if (x <= 0) return x + 1;
    else return f(f(x - 2));
}

例如，$f(1)$ 的计算过程如下，返回值为 1，并且在计算过程中函数 $f$ 被调用了 3 次。

$$f(1)\to f(f(-1))\to f(0)\to 1.$$

回答以下问题：

1. 计算 $f(2)$ 在求值过程中函数 $f$ 被调用的次数。

2. 证明对于每一个非负整数 $n$，$f(n)$ 的返回值都是 1。

3. 设 $n$ 是一个非负整数。表达 $f(n)$ 在求值过程中函数 $f$ 被调用次数的公式，使用 $n$ 表示。

4. 设 $n$ 是一个非负整数。表达 $f(n)$ 在使用按名调用策略（call-by-name）而非按值调用策略（call-by-value）时，函数 $f$ 被调用次数的公式，使用 $n$ 表示。

5. 给出一个程序的例子，该程序在按值调用策略下不终止，但在按名调用策略下终止。