跳转到内容

PPCA 2020

来自ACM Class Wiki

时间

  • 7月6日 -- 8月14日（ACM班），7月6日 -- 7月31日（工科）
  • 周一至周五
  • 上午：9:00 -- 12:00
  • 下午：14:00 -- 17:00
  • 机考日(第二周开始，每周周四)下午：13:00 -- 18:00 可提前离场，机考后有讲题时间

地点

  • ZOOM 会议室

分数构成

ACM班：

  • 25% RISCV模拟器
  • 30% 机考
  • 45% 分组大作业

工科：

  • 30% RISCV模拟器
  • 30% 机考
  • 40% 分组大作业


联系方式

Name Email
郑文鑫 peterzheng98@sjtu.edu.cn
董海辰 oscardhc@sjtu.edu.cn
赖睿航 masterjh5574@sjtu.edu.cn
张志成 zhangzhicheng1@sjtu.edu.cn
唐泽 mintgreen@sjtu.edu.cn
傅凌玥 fulingyue@sjtu.edu.cn
刘成锴 liuchengkai@sjtu.edu.cn
张扬天 zjhz-zyt@sjtu.edu.cn
郭睿涵 guoruihan@sjtu.edu.cn
王一 refraction334@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
    • …
  • 演讲时间安排在 11:30 -- 12:00，16:30 -- 17:00（除周四）
  • PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲

RISCV大作业

  1. 正确性测试：实现一个可以正确实现模拟RISCV指令集功能的模拟器，可以通过正确性测试的所有数据。
  2. 五级流水实现：简单实现了RISCV 5级流水线设计，遇到hazard的时候有行之有效的处理（比如直接暂停流水）。
  3. 分支预测实现：至少实现一个两位饱和计数器的分支预测。 code review的时候需要：
    • 讲清楚你的五级流水实现方式，分支预测实现方式
    • 向助教展示必要的中间内容
  4. Bonus。
  • 执行流程：
    • 从标准输入读入机器指令
    • 从内存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指令集，弄懂机器指令的执行流程
    • 写一个不带流水的简易模拟器
    • 加上五级流水
    • 写写bonus，欢迎实现各种个性化的功能
    • 文件:一点小小的帮助.pdf
  • 参考书籍：
    • 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


DHT

Person in Charge - 赖睿航

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

Basic 编译器

负责人：傅凌玥，郑文鑫

项目要求

  • 完成一个 BASIC 语言的简易编译器，包括从源代码到 AST 到 RISC-V 汇编。
  • 需要检测出语法错误，通过语法阶段的正确性测试。
  • 不允许使用 ANTLR 等现成的解析器。

项目内容

  • 完成一个语言解析器(parser)，并生成抽象语法树(AST)；
  • 遍历AST来检测语法错误；
  • 将AST转为无限寄存器的RISC-V;
  • 实现简单的 mem2reg（即所有的变量都存在内存中，需要时再放入寄存器中），生成RISC-V汇编.
  • 最后，把RISC-V汇编读入前一个项目（RISC-V模拟器），并检测运行结果的正确性。

项目评分

90%测试点正确性和完成度，10%的code review/report评分。

光线追踪

负责人：郑文鑫

五子棋

负责人：张志成

项目要求

项目内容

  • 实现Minimax搜索，alpha-beta剪枝，迭代加深搜索
  • 蒙特卡洛搜索树(MCTS)，强化学习作为Bonus
  • 前端的形式包括但不限于网页、小程序、手机App

项目评分

60%算法实现(70%：超过50%胜率打败baseline，30%Code Review), 40%前端展示。

检索自“https://acm.sjtu.edu.cn/w/index.php?title=PPCA_2020&oldid=4129”