言語処理系特論（Language Processor）[2408]

＜授業のねらい及び具体的な到達目標＞

本講義で扱う言語処理とは，計算機でプログラムを実行する際に利用するコンパイラを指す。コンパイラは，CやC++などのプログラミング言語で記述されたソースプログラムを計算機が理解可能な機械語に翻訳するソフトウェアで，その特徴の１つに，最適化処理がある。
最適化処理とは，実行不要な命令の削除に加え，計算機のアーキテクチャに合わせて命令の実行順序を変更することによってプログラムの実行時間を短縮する処理である。計算機アーキテクチャには，命令セット，メモリ，キャッシュメモリ，レジスタファイルといった計算機の基本的な構造に加え，スーパスカラ，メニイコア，SIMD，SMPなど，並列実行のための機構及び構成がある。最適化処理では，これらの計算機アーキテクチャを有効活用することで実行時間の短縮を図っている。
しかし，コンパイラはソースプラグラムに記述された静的な情報しか利用できないことに加え，有限の時間及び有限のメモリ空間で処理しなければならないため，最適化処理による実行時間の短縮には限界がある。したがって，計算機の性能を最大限引き出すためには，コンパイラの最適化処理のみに頼るのではなく，計算機アーキテクチャとコンパイラの最適化処理を理解した上で，ソースプログラムを計算機アーキテクチャに合わせて記述する必要がある。
本講義では，字句解析，構文解析，意味解析といったコンパイラの基礎について解説するとともに、メニイコア，SMP，GPGPU等の最新の計算機アーキテクチャを，計算機発展の歴史を踏まえて紹介する。スーパスカラやSIMD機構など、プロセッサが持つ演算機構を効率的に利用するためのコンパイラ最適化処理を理解すると，プログラムの実効性能を引出す上でボトルネックとなる部分が見えてくることから，計算機仕様とコンパイラ最適化処理の関係を理解することは，効率的なプログラムを作成する上で非常に重要である。

‘Language processor’ in this lecture means compiler which translates source program written in programing language such as C or C++ to machine language in order to execute on computer. One of features of compiler is optimization. In the optimization process, dead code elimination, the reorder of executing instructions considering architecture of computer, and so on are applied to execution program in order to improve execution performance.
The computer architecture means detail specification of computer system which involves instruction set, memory, cache memory, resister file, etc. In addition, the computer system has superscalar, many-core processer, SIMD and SMP for parallel execution. The performance improvement is achieved by effective utilization of the computer architecture.
However the compiler can utilize only static information described on source code and the compiler has to process the optimization with limited time and limited memory resource. Therefore, important thing to derive the execution performance is not only the optimization of compiler but also source program description suitable to computer architecture.
This lecture introduces basic operation of compiler such as lexical analysis, syntax analysis and semantic analysis and also the computer architectures are introduced based on evolutionary history of computer system. By understanding the relation between compiler optimization and computer architecture, bottleneck of performance improvement becomes clear on source code.

＜授業計画及び準備学習＞

1 計算機発展の歴史とアーキテクチャの変遷
2 プログラミング言語の歴史
3 コンパイラの構成と字句解析
4 後置記法(逆ポーランド記法)
5 オートマトン
6 構文解析と意味解析
7 命令レベル最適化
8 ループ構造変換最適化
9 メモリ構造とキャッシュメモリ向け最適化
10 自動並列化技術
11 オブジェクト指向言語の処理方式
12 仮想計算機JavaVM(Virtual Machine)の概要
13 Java実行時のメモリ割当方式とGC(Garbage Collection)
14 Javaの最適化技術(HotSpotVM及びJITコンパイラ)

1. Evolutionary history of computer and the change of computer architecture
2. History of programming language
3. Configuration of compiler and lexical analysis
4. Postfix notation (Reverse Polish notation)
5. Automaton
6. Syntax analysis and semantic analysis
7. Instruction level optimization
8. Loop structure conversion
9. Memory structure and effective utilization of cache mamory
10. Automatic parallelization by compiler
11. Processing method of object-oriented programming language
12. Virtual machine system (Java VM)
13. Memory allocation method of Java VM and garbage collection
14. Optimization features of Java (HotSpotVM and JIT Compiler)

＜成績評価方法及び水準＞

授業の出席点とレポートによって評価する。

Grade is evaluated by attendance at the lecture and report.

＜教科書＞

特定の教科書を使用せず，必要に応じて授業の際に資料又は文献を配布する。

Materials and reference documents are distributed as necessary.

＜参考書＞

１．中田育夫：コンパイラの構成と最適化，朝倉書店，1999年
２．今城哲二，布広永示，岩沢京子，千葉雄司；コンパイラとバーチャルマシン，オーム社，2004年
３．金田康正，片桐孝洋，黒田久泰，山本有作，五百木伸洋，並列処理　−高速化と性能向上のために　　　−，コロナ社，2010年

＜オフィスアワー＞

授業に対する質問・意見はメールで随時受け付けます。 メールアドレスは，第1回目の講義の時に連絡します。

Consultation and questions about this lecture are accepted at any time by e-mail.
The e-mail address will be announced at the first lecture.

＜学生へのメッセージ＞

最先端の計算機アーキテクチャとコンパイラの最適化・自動並列化技術に興味がある学生の受講を歓迎します。

Graduate students interested in computer architecture, optimization of compiler and automatic parallelization are well come.