東京大学 情報理工学系研究科 創造情報学専攻 2017年8月実施 筆記試験 第3問

标签：

• Tokyo-University
• Pipeline-Hazards
• Register-Renaming
• Kalman-Filter
• Regular-Grammar-and-Regular-Language
• Public-Key-Infrastructure
• Traveling-Salesman-Problem
• Divide-and-Conquer
• Vector-Quantization

Author

tomfluff, itsuitsuki, 祭音Myyura

Description

原題（日本語） Select four items out of the following eight items concerning information systems, and explain each item in approximately from four to eight lines of text. If necessary, use examples or figures.

1. Pipeline hazard
2. Register renaming
3. Kalman filter
4. Regular grammer and regular languages
5. Public key cryptography and certification authority
6. Traveling salesman problem
7. Divide and conquer method
8. Vector quantization

题目描述

从下列八个信息系统相关主题中任选四个，每个用约 4～8 行说明；必要时可使用示例或图。

1. 流水线冒险。
2. 寄存器重命名。
3. 卡尔曼滤波。
4. 正则文法与正则语言。
5. 公钥密码与认证机构。
6. 旅行商问题。
7. 分治法。
8. 向量量化。

Kai

Pipeline hazard

A pipeline hazard prevents an instruction from proceeding in its intended pipeline cycle unless the processor resolves the conflict, for example by stalling, forwarding a result, or flushing incorrectly fetched instructions. There are several types of hazards:

1. Structural hazard - Occurs when two instructions need the same hardware resource in the same cycle.
2. Data hazard - Occurs when an instruction needs a value that an earlier instruction has not yet produced.
3. Control hazard - Occurs when a branch or jump makes the next instruction address uncertain.

Register renaming

Reuse of one architectural register for unrelated values creates false write-after-write (output-dependence) and write-after-read (anti-dependence) hazards. A compiler can assign different registers to such values; in a processor, dynamic register renaming maps different definitions to distinct physical registers. This permits more out-of-order execution while preserving program results. Renaming does not remove a true read-after-write dependence.

Kalman filter

Please refer to CI 2011-4, (2).

For the linear model $x_t=F_tx_{t-1}+B_tu_t+w_t$, $z_t=H_tx_t+v_t$, predict $\hat x^-_t=F_t\hat x_{t-1}+B_tu_t$ and $P^-_t=F_tP_{t-1}F_t^T+Q_t$. Then $K_t=P^-_tH_t^T(H_tP^-_tH_t^T+R_t)^{-1}$, $\hat x_t=\hat x^-_t+K_t(z_t-H_t\hat x^-_t)$, and $P_t=(I-K_tH_t)P^-_t$.

Here $w_t$ and $v_t$ are zero-mean white noises with covariances $Q_t,R_t$, mutually uncorrelated and uncorrelated with the initial estimation error; the innovation covariance is invertible. These equations give the optimal linear estimate. For a Gaussian initial state and Gaussian noises, they give the exact conditional mean and covariance as well.

Regular grammar and regular languages

A regular language is a formal language (set of sequences of symbols, a subset $L$ of the alphabet $\Sigma$'s Kleene star $\Sigma^*$) whose elements are able to be accepted by a finite automaton (DFA or NFA).

A regular grammar is defined by $G=(N,T,S,P)$:

• $N$ are non terminal symbols (variables).
• $T$ are terminal symbols.
• $S$ is a start symbol.
• $P$ is the production rule for all symbols, where the rules only include these kinds:
  • $A\to aB$ where $a$ is a terminal and $A,B$ are nonterminals; this is a right-linear rule (a left-linear grammar instead uses $A\to Ba$);
  • $A\to a$ (a nonterminal generates a terminal)
  • $A\to\epsilon$.

A grammar must consistently use the right-linear form or consistently use the left-linear form; mixing the two need not generate a regular language. Regular grammars generate exactly the regular languages.

Public key cryptography and certification authority

Public key cryptography secures communication over a public channel using a public/private key pair for each entity, not one shared public key. In a public-key encryption scheme, the public key encrypts and the private key decrypts; in a signature scheme, the private key signs and the public key verifies. Security may rely on factoring, discrete logarithms, or another hard problem. A certification authority signs a certificate binding an identity or domain name to a public key. In TLS, the client validates the certificate chain before trusting that binding.

Traveling salesman problem

The TSP problem is a classic problem in computer science, which describes a traveling salesman who wants to get the shortest path through each city as a node once and finally back to the starting node. The optimization problem is NP-hard, and its decision version is NP-complete. Suppose there are $N$ cities; enumerating the $(N-1)!$ tours from a fixed starting city and evaluating each in $O(N)$ time gives an $O(N!)$ brute-force algorithm and an $O(N^22^N)$ state-compression DP algorithm exist.

Some heuristic solutions exist which reduce the runtime but may not find the optimal solution.

Divide and conquer method

Please refer to CI 2008-4, (1).

Divide and conquer splits a problem into smaller subproblems, solves them recursively, and combines their results. Merge sort, for example, satisfies $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$.

Vector quantization

Used in compression algorithms. Vector quantization assigns each vector $x$ to its nearest representative (codeword) $c_i$ in a finite codebook: $i=\arg\min_j\lVert x-c_j\rVert$. The encoder stores the index $i$ and the decoder reconstructs $c_i$, yielding lossy compression. A codebook can be learned by Lloyd's algorithm (k-means).