PPCA 2021

时间

• ACM：6月28日-8月7日， 周一到周五，共6周
• 工科： 6月28日-7月24日，周一到周五，共4周
• 除机考日外：上午：9:00~12:00 下午：14:00~17:00
• 机考日（第二周起每周四）：上午：9:00~11:00 下午：13:00~18:00
• 机考可提前离场，机考后有讲题时间
• PPCA介绍

地点

• 软件学院一楼5-104机房 （在一楼）

分数构成

• 1. RISC-V CPU模拟器（第1周、第2周） 25%
• 2. Verilog硬件描述语言 小作业（第2周） 5%
• 3. 机考（第2周起，工科共3次，ACM班共5次） 30%
• 4. 分组项目四选一（四个项目均为工科第3周第4周，ACM班第3-6周） 40%
  • AI对战 （工科、ACM班可选）
  • Raytracer 光线追踪 （工科、ACM班可选）
  • DHT 分布式哈希表 （ACM班可选）
  • Raft分布式一致性协议 （ACM班可选）
• 5. 签到扣分：有事请提前与当班助教请假，有签到，无故缺席将被扣除分数。（会有值班表）

联系方式

Name	Email
周聪	cong258258@sjtu.edu.cn
史涵雯	shihanwen@sjtu.edu.cn
陈雪阳	anoxiacxy@sjtu.edu.cn
徐若凡	aqua_blue@sjtu.edu.cn
张洪鑫	icefox@sjtu.edu.cn
许振宇	battlin@sjtu.edu.cn
闵乐钧	aik2mlj@sjtu.edu.cn
林春茹	linchunru@sjtu.edu.cn
黄臻	xmhuangzhen@sjtu.edu.cn
杨新宇	yang_xinyu@sjtu.edu.cn

机考

• 机考时间：
  • 第二周开始，每周四
  • 下午：13:00 -- 18:00
  • 可提前离场
• 机考形式：
  • AB卷
  • A卷为传统算法题，包含三道题，赛制同程序设计/数据结构课
  • B卷为非传统综合应用题，包含一道题
  • 最终评分只与每个人在两组试卷的答题者中的排名有关
  • 对于B卷，分数将根据答案的优劣评判（这意味着，任何格式正确的答案大都是有点分数的）
  • 如果某道题提交的答案得分达到了一条预先设定的Ground Truth的线（如果真的有的话），则此次机考这位参赛者可以不参加排名，成绩按满分计
• 机考允许并鼓励：
  • 思考创新
  • 寻找规律
• 机考严禁：
  • 交流
  • 查询资料
  • 查看其它同学代码
  • 把自己代码给同学看
  • 帮助同学计算答案
  • 其它一切不诚实行为

自选主题演讲

• 主动向助教报名
• 选择主题后需要向助教申请:
• 可以参考的主题有：
  • Some C++ features and design models: RAII, smart pointer, rvalue reference
  • Concurrency: mutex, lock, conditional variable, etc.
  • Common types of ISA
  • Other programming languages
  • …

• PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲

• 董易昕：Compression-algorithms
• 陈垍铮：浅谈AI与音乐创作
• 唐嘉铭：AI 结课 pre
• 仇天元：RT 结课 pre
• 林超凡：DHT 结课 pre
• 吴叶鑫：Raft 结课 pre

RISC-V CPU模拟器

• 内容：完成一个 RISCV 模拟器
  • 文件:Riscv-spec-v2.2.pdf
  • 文件:PPCA2019-RISC-V.pdf
  • 文件:RISCV-Simulator-2020.pdf
  • package for riscv simulator

• OJ 地址：2021 PPCA RISCV Simulator

• 评分：
  • 正确性测试：使用 C++ 实现一个可以正确实现模拟RISCV指令集功能的模拟器，可以通过正确性测试的所有数据。
  • 根据乱序与否分为两个版本可选：:
    • 基本版本：五级流水，至少实现 2 位饱和计数器分支预测
    • 高级版本：托马斯洛 Tomasulo 乱序执行

• 五级流水实现：简单实现了RISCV 5级流水线设计，遇到hazard的时候有行之有效的处理（比如直接暂停流水）。
• 分支预测实现：至少实现一个两位饱和计数器的分支预测。

• 可能的Bonus（五级流水）：高级分支预测，数据前传（forwarding），真流水（即在一个周期内可以任意交换五个流水部分执行的先后顺序）。

• code review的时候需要：
  • 讲清楚你的五级流水实现方式，分支预测实现方式。
  • 向助教展示必要的中间内容。

• 执行流程：
  • 从标准输入读入机器指令
  • 从内存00000000处开始取指令执行，每次连续取4个2位十六进制数，组成一条指令（如取到“37 17 00 00”，拼成32位指令“00001737”）
  • load/store指令内存访问部分（第四级）请用三个周期模拟
  • 执行到指令0ff00513（ li a0,255 ）时，向标准输出 输出程序的返回值（一个0-255的非负整数），结束模拟。注意：
    • 程序的返回值存在a0寄存器里，但是寄存器是32位的，返回值是8位的，所以你应该输出a0的后八位。例如，你的a0寄存器是int数组reg中的reg[10]，你应该输出的是((unsigned int)reg[10]) & 255u。

• 建议流程：
  • 熟悉RISCV指令集，弄懂机器指令的执行流程
  • 写一个不带流水的简易模拟器
  • 加上五级流水：文件:一点小小的帮助.pdf
  • 写写bonus，欢迎实现各种个性化的功能，如尝试真·并行

• 参考书籍：
  • J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 5th Edition
  • J. L. Hennessy and D. A. Patterson, Computer Organization and Design：The Hardware/Software Interface, 5th Edition

Verilog小作业

• Verilog HDL（简称 Verilog）是一种硬件描述语言，用于数字电路的系统设计。可对算法级、门级、开关级等多种抽象设计层次进行建模。
• 学习语法，实现简单的时序逻辑与组合逻辑电路，如加法器
• Some_hint_for_Verilog
• OJ 地址：2021 PPCA Verilog Practice
• 参考资料：https://hdlbits.01xz.net/wiki/Problem_sets

AI BATTLE--Rodirou

项目要求

• 实现指定算法的AI
• 在线AI对战，获取更好的排名
• 完成机器学习相关任务

项目内容

• 实现Minimax搜索，alpha-beta剪枝
• 蒙特卡洛搜索树(MCTS)，强化学习作为Bonus

项目评分

• 工科
  • 实现指定算法(会有code review) 60%
  • 打败baseline(会分几档) 20%
  • 最终排名 20%
• ACM班
  • 同工科全部内容 70%
  • ML-related Task 30%

• Rodirou.zip

Raytracer 光线追踪

负责人：闵乐钧 林春茹

• Raytracer
• Github Template

DHT

Overview

• A DHT can be viewed as a dictionary service distributed over a network: it provides access to a common shared key->value data-store, distributed over participating nodes with great performance and scalability.
• From a user perspective, a DHT essentially provides a map interface, with two main operations: put(key, value) and get(key). Get will retrieve values stored at a certain key while put (often called announce) will store a value on the network. Note that many values can be stored under the same key.
• There are many algorithms to implement DHT. For this project, you are required to implement at least Chord protocol. You are also required to implement an application of DHT or implement another protocol. Finally, you should write a report for about one page.

More info in Wiki:DHT

Assignment

• Use Go to implement a Chord DHT with basic functions.
• Use this DHT to implement an easy application, or implement another protocol.

Syllabus

• Learn GoLang.
• Implement Chord protocol.
• Implement an application of DHT or implement another protocol.

Score

GitHub repository for test: DHT-2020

• 70% for the Chord Test (60 + 10).
  • 60% + 10%: 60% for basic test and 10% for advance test.
  • Basic test: naive test without "force quit".
  • Advance test: "Force quit" will be tested. There will be some more complex tests.
• 20% for the application/second protocol.
• 10% for a short report and code review.

Tests

Unluckily, DHT tests cannot run successfully under Windows. So if you want to run tests by yourself, it is recommended to run tests under a Linux virtual machine, or employ a remote server.

If you want to debug tests by yourself, you can still use GoLand under virtual machine, or use Delve (a GoLang debugger) + GoLand if you employed a remote server.

Contact TA if you find any bug in the test program, or if you have some test ideas, or if you think the tests are too hard and you want TA to make it easier.

Basic Test

The current test procedure is:

• There are 5 rounds of test in total.
• In each round,
  • 20 nodes join the network. Then sleep for 10 seconds.
  • Put 200 key-value pairs, query for 160 pairs, and then delete 100 pairs. There is no sleep time between contiguous two operations.
  • 10 nodes quit from the network. Then sleep for 10 seconds.
  • (The same as 2.) Put 200 key-value pairs, query for 160 pairs, and then delete 100 pairs. There is no sleep time between contiguous two operations.

Advance Test

Not finished yet.

How to Test Your Chord?

• Clone this repository using git clone https://github.com/MasterJH5574/DHT-2020.git.
• Set the environment variables GOROOT and GOPATH correctly.
• Under GOPATH, run go get -u -v github.com/fatih/color in shell to install the color package.
• Replace $GOPATH/src/main/userdef.go with your own userdef.go. Do not modify $GOPATH/src/main/interface.go.
• Copy your Chord package(s) into $GOPATH/src directory.
• Under GOPATH, run go build main to generate the executable main. Then use ./main -test basic or ./main -test advance or ./main -test all to run the corresponding test. (Or you can use go run main -test [testName] to run tests directly without generating the executable main.) (Or you can use GoLand to run the tests.)

About Go Remote Debug

Please reference this guide.

Reference

• Learn Go

> A Tour of Go
> Go package docs
> Books about Go

• DHT models

> Chord
> Pastry
> Kademlia

• Related project framework

> Dixie
> CMU
> MIT

Raft

负责人：杨新宇

• Total Requirement
• Raft Info