東京大学 情報理工学系研究科 創造情報学専攻 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

Pipeline hazard refers to a situation where dependencies in a program result in incorrect execution in pipeline or out-of-order execution. 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

In compilation, the assembly code may have the same register used in disjoint code parts, which causes unneccesary dependency.

For out-of-order execution, reuse of one architectural register creates false write-after-write (output-dependence) and write-after-read (anti-dependence) hazards. Register renaming maps different definitions to distinct physical registers and removes those hazards; it does not remove a true read-after-write dependence.

(These are anti-dependency and output-dependency, which are false dependencies so they can be eliminated by register renaming.)

Register renaming can resolve these hazards by renaming the shared register in one part with another free register to enable out-of-order execution or pipelining.

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$.

Regular grammar and regular languages

Note: Bracketed information is optional. 选写括号内

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 regular language can be generated by a regular grammar.

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. A public key can encrypt to its owner or verify its signatures; the private key decrypts or signs. 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; a $\Theta(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).