跳转到内容

PPCA 2019

来自ACM Class Wiki

时间

  • 7月1日 -- 8月9日
  • 周一至周五
  • 上午：8:30 -- 11:30
  • 下午：14:30 -- 17:30
  • 机考日(第二周开始，每周周四)下午：13:00 -- 18:00 可提前离场

地点

  • 软件学院机房5-104

分数构成

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

日程记录

https://docs.google.com/spreadsheets/d/1xUqF6mjutLOQPyFeoQMwpwQjOrizb219oUZ5SKBsUXI/edit?usp=sharing

联系方式

Name Email
赵寒烨 fineartz@sjtu.edu.cn
汪伟杰 wangnick@sjtu.edu.cn
任云玮 2016renyunwei@sjtu.edu.cn
杨孟天 lepetitprince517@sjtu.edu.cn
龚勋 gongxun@sjtu.edu.cn
张文涛 zwt1999@sjtu.edu.cn

机考

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

自选主题演讲

  • 主动向助教报名
  • 主题在助教给定的若干个主题中选（其他主题也可以向助教申请）:
    • Some C++ features and design models: RAII, smart pointer, rvalue reference
    • CMake / makefile
    • Shell scripting tutorial
    • Concurrency: mutex, lock, conditional variable, etc.
    • Common types of ISA
    • …
  • PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲
  • 这一部分的分会作为下面的RISCV大作业评分的参考（作为Bonus）

RISCV大作业

  1. (60%)正确性测试：实现一个可以正确实现模拟RISCV指令集功能的模拟器，可以通过正确性测试的所有数据。
  2. (40%)五级流水实现：简单实现了RISCV 5级流水线设计，遇到hazard的时候有行之有效的处理（比如直接暂停流水）。 code review的时候需要：
    • 讲清楚你的五级流水实现方式
    • 向助教展示必要的中间内容
  3. Bonus：
    • 动态分支预测
    • 自选主题演讲
  • 执行流程：
    • 从标准输入读入机器指令
    • 从内存00000000处开始取指令执行，每次连续取4个2位十六进制数，组成一条指令（如取到“37 17 00 00”，拼成32位指令“00001737”）
    • load/store指令内存访问部分（第四级）请用三个周期模拟
    • 执行到指令00c68223（ sb a2,4(a3) ）时，向标准输出 输出程序的返回值（一个0-255的非负整数），结束模拟。注意：
      • 程序的返回值存在a0寄存器里，但是寄存器是32位的，返回值是8位的，所以你应该输出a0的后八位。例如，你的a0寄存器是int数组reg中的reg[10]，你应该输出的是((unsigned int)reg[10]) & 255u。
  • 评测
    • Online Judge Contest - RISCV
    • 提交时填写公开的github地址，请确保你的仓库里有能正确生成可执行文件code的makefile
    • 评测时运行code文件，提供标准输入，比对标准输出
  • 建议流程：
    • 熟悉RISCV指令集，弄懂机器指令的执行流程（参考： 自己编译测试数据的方法）
    • 写一个不带流水的简易模拟器
    • 加上五级流水
    • 写写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


机器学习系统

负责人 - 杨孟天

项目说明

DHT

newest version will be seen in github

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, where Kademlia DHT algorithm requires to contact only O(log(N)) nodes for a get operation, N being the number of nodes in the network. This property makes DHTs very scalable as demonstrated. Other algos are shown in reference.

More info in Wiki:DHT

Totally info will be shown in Github Wiki

Target

  • Use go-lang to implement a DHT with basic functions
  • Use this DHT to implement an easy application

Syllabus

Schedule

  • Learn about Golang and at least one DHT protocol

> Project 1(Not constrained): get close to golang: implement a client-server protocol using golang. With naive tests.

> forward message and mutli-threads(2 with client and server)

  • Implement a DHT protocol in Go

> Project 2: implement DHT: using any one model is allowed. With naive and strong tests.

  • Build a higher level application on top of your DHT

> Project 3*: implement an application. No test. E.g. chatroom, torrent, dht-filesystem.

  • Bonus

> Project 4*: implement DHT with another algorithm (as mentioned above in overview), or optimize your application.

Reference

  • Learn Go

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

  • DHT models

> Chord
> Pastry
> Kademlia

  • Related project framework

> Dixie
> CMU
> MIT

Test(beta)

Repo

> Test Repo

Range(Beta)

  • nodes in DHT network >= 50
  • <key, value> in DHT network >= 1500
  • Give some time for your network to resume stable.

Contents

Requirements

  1. Implement this interface in interface.go
   type dhtNode interface {
       Get(k string) (string, bool)
       Put(k string, v string) bool
       Del(k string) bool
       Run(wg *sync.WaitGroup)
       Create()
       Join(addr string) bool
       Quit()
       Ping(addr string) bool
   }
  1. Overwrite in userdef.go
   func NewNode(port int) *dhtNode{
        // replace with your own code
   }

Tests

  • standard test

> get, put, del, join, quit, ping

  • standard test of additive functions

> append info in <k, v>
> del_append info in <k,v>

  • additive test

> get, put, del, join, quit, ping
> force quit
> load(max nodes and max data)
> unstable put and get
> mixed put, get, join, quit


Raft 一致性算法

负责人 - 任云玮、汪伟杰

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