跳转到内容

PPCA 2018

来自ACM Class Wiki

时间

  • 7月2日 -- 8月10日
  • 周一至周五
  • 上午：8:30 -- 11:30
  • 下午：14:30 -- 17:30
  • 机考日下午：13:00 -- 18:00 可提前离场

地点

  • 软件学院机房5-104

分数构成

  • 20% MIPS
  • 30% 机考
  • 20% 贡献题目
  • 30% 分组大作业

日程记录

https://docs.google.com/spreadsheets/d/1W94osTqFx-CSP6mG2cvmiVTcpwGDpFTZ9aHCVZNRYMY/edit?usp=sharing

联系方式

Name Email
刘啸远 lxy9843@sjtu.edu.cn
冯思远 Hzfengsy@sjtu.edu.cn
范舟 zhou.fan@sjtu.edu.cn

机考

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

自选主题演讲

  • 主动向助教报名
  • 主题不限，专业相关即可
  • PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲
  • 这一部分的分会作为MIPS大作业评分的参考

MIPS大作业

  1. (60%)正确性测试：实现一个可以正确实现模拟MIPS功能的解释器，可以通过正确性测试的所有数据。
  2. (15%)MIPS流水线实现：简单实现了MIPS 5级流水线设计，遇到hazard的时候有行之有效的处理（比如直接暂停流水）。
  3. (15%)Code Review：
    • 向助教说明自己实现的细节、特点（5%）
    • 正确理解了MIPS的5级流水线的5个阶段的划分，Hazard出现的原因(10%，没有实现五级流水但是能讲清楚5%)
  4. (10%)综合评价
    • （推荐）如果为至少3位同学（实名）提供了耐心的帮助，那么此项可以获得满分。
    • （推荐）如果进行了自选主题演讲，那么此项可以获得满分。
    • 如果成功实现了不同于Predict Not Taken/Predict Taken的分支预测算法，并且能讲清楚大致的实现细节，那么此项可以获得满分
    • 如果成功实现了并发的五级流水（或者其他的多级流水处理架构），并且能讲清楚大致的实现细节，那么此项可以获得满分注意：如实现并发版本请新开一个branch，并在code review时展示，不要在OJ上提交并发版本，后果自负
    • 如果设计并实现了不同于五级流水的多级流水架构（比如龙芯的九级流水），而且此架构在复杂性上大于五级流水，那么此项可以获得满分
    • 如果成功实现了Tomasulo算法以及对应的多级流水，并且能讲清楚大致的实现细节，那么此项可以获得满分

机器学习系统

负责人 - 冯思远

目标

  • 实现一个简化的TensorFlow框架，Python接口同TensorFlow保持一致
  • 实现简单的Logistic Regression、Neural Network、CNN等简单功能
  • 完成简单的GPU编程

评分

  • 依据测试数据的时间和空间进行排名
  • 依据情况设置baseline

Week 1 编程语言、机器学习基础

  • 学习Python3编程，Python3的面向对象编程，Python教程（该教程使用Python2）[1]，面向对象[2]
  • 了解机器学习基础知识
  • 分别使用TensorFlow和numpy使用CNN和Logistic Regression实现MNIST的识别代码[3]
  • 7.20晚23:59前邮件至Hzfengsy@sjtu.edu.cn

Week 2 自动求导

  • lecture[4]
  • assignment[5]
  • 7.27晚23:59前邮件至Hzfengsy@sjtu.edu.cn
  • 前两周安排较空，可尽快完成出题任务或提前完成后续工作

Week 3-4 自主实现机器学习框架

  • 通过相应测试数据（数据尚未准备完成）
  • 按排名给分
  • 可实现高级功能（如TensorBoard）可获得Bonus
  • 8.10晚23:59前邮件至Hzfengsy@sjtu.edu.cn

Distributed Hash Table

DHT 简介

  • Distributed hash table (DHT) 是一类去中心化的分布式系统，DHT 在一个去中心化的节点网络上提供 Key-Value 的存储与查找功能（与 hash table 类似）。
  • DHT 可以应用于于节点数量很大的去中心化网络中，维护整个 <key, value> 映射的责任分散在网络中的节点上。
  • 由于结构设计的稳定性，在新节点加入网络、原有节点退出网络、个别节点出现故障的情况下，DHT 仍能稳定地提供服务。
  • DHT 作为一个底层架构，可以被用于搭建更复杂的服务：如网络内容缓存、分布式文件系统、即时聊天系统，以及 P2P 文件分享（如 BitTorrent）和内容分发系统。

更多介绍：Wikipedia:Distributed hash table

目标

  • 单人任务
  • 使用 Go 语言实现一个具有基础功能的 DHT
  • 以实现好的 DHT 为底层架构搭建一个具体的分布式应用

Plan

References

Stages

  • Learn about Golang and at least one DHT protocol
  • Implement a DHT protocol in Go
  • Write test script to check correctness and robustness
  • Build a higher level application on top of your DHT

Test

测试规模

  • DHT 网络中最多同时存在的节点数 >= 50
  • DHT 网络中最多同时存在的 <key, value> 对数量 >= 1500

测试内容

  • 节点加入网络
  • 节点退出网络
  • 向 DHT 网络中插入 <key, value> 对
  • 从 DHT 网络中查询特定 key 对应的 value
  • 从 DHT 网络中删除特定 key 对应的 value

以上测试内容交替进行

测试流程如下

  • 初始时由一个 DHT 节点组成网络
  • 循环五次：
    • A. 向网络中加入 15 个节点
    • B. 选择 5 个节点退出网络
    • 每次一个节点加入/一个节点退出后等待 3s
  • 上述的 A, B 操作之后均进行：
    • 等待 30s
    • 向 DHT 网络中插入 300 个键值对
    • 在网络中现有的键中随机选择 200 个进行查询操作并验证正确性
    • 从网络中现有的键中随机选择 150 个删除

分数构成

  • 80% - 基础 DHT 并通过测试
  • 20% - 提高部分，可选择以下之一：
    • 在 DHT 上搭建一个具体应用
    • 在 Chord DHT 基础上提升安全性
    • 将 DHT 节点保存在内存的数据通过 Buffer 定期保存在硬盘文件中

Raft 一致性算法

Raft 简介

  • 副本一致性：对于一个分布式系统，同一份数据通常会在集群中不同的节点上不止一份备份，保证副本一致性即确保在任意时刻从不同的节点中读取同一份数据的结果是相同的。
  • Raft算法：一个使得副本满足一致性的分布式算法。
  • 论文：In Search of an Understandable Consensus Algorithm(Extended Version)

目标

  • 使用C++实现Raft算法的基础版本
  • 熟悉C++工程管理等
  • 按照完成程度与code review评分

Week 1

  • 学习C++多线程编程
    • C++ Concurrency in Action: Chapter 1~4
    • 概览 Boost.Thread 的文档
  • 学习使用CMake管理C++工程
    • 参考资料：CMake Practice
  • 配置环境
    • CMake
    • Boost
    • grpc 或其它rpc框架
    • 备注：推荐使用Linux或macOS或WSL
  • 阅读Raft论文前5节

Week 2

  • 尽可能实现Raft算法Candidate部分
  • 要求
    • Server：读入集群配置文件；start；shutdown（配置文件格式自定，建议使用json等格式）
    • 能够开始一次选举并在正常情况下选出一个leader
    • 能够正确处理收到的RequestVote RPC
    • 暂时可以不实现log写入硬盘的部分
    • 其它和选举无直接关联的部分可以不实现，例如client的请求
  • 周五Code Review（非正式，不算分）
  • 参考资料：https://github.com/ongardie/dissertation#readme

NES on FPGA

TA

林耘丰

Intro

  • NES: Nintendo Entertainment System, a.k.a. Famicom(FC), an 8-bit home video game console.
    • CPU: Ricoh 2A03 8-bit processor (MOS Technology 6502 core)
    • Media: ROM cartridge ("Game Pak")
    • Best-selling game: Super Mario Bros. (1 2 3)
  • FPGA: field-programmable gate array, an integrated circuit that can be configured using a hardware description language (HDL).
    • We have: Digilent Basys 3
    • I/O: VGA output, USB-UART Bridge

Task

work solo

  • Implement an Nintento Entertainment System emulator on FPGA that runs common NES games (NROM).
  • Alternatively, implement your own 8-bit game console that runs your own games.

Requirements

  • use the 8-bit processor (6502)
  • video output in VGA
  • receive input from UART bridge as joystick input

Schedule

Phase 1

  • Learn a HDL (preferably Verilog).
  • Integrate the existing 6502 Core.
  • Use UART port to load ROM (the program to execute) into the memory.
  • Use UART port to receive joystick input (emulated by keyboard input from PC).

Phase 2

  • Implement the NES PPU (Picture Process Unit) on FPGA, which generates video signal with 240 lines of pixels.
  • Integrate the existing VGA output module.

Alternatively, implement your own graphic processor and write your own games.

Phase 3

  • Testing
  • Presentation

Optional

If there's time, you can

  • Implement mappers to support more games.
  • Implement the APU (Audio Process Unit) that generate sounds. (how to output?)

Grading

Grading rules: [6]

Tools

Tutorial & Guide

Notes

  • project template repository: [12]
  • avoid combinatory logic, use sequential logic if possible. (i.e. write code mainly in "always @*" block)
  • because CPU is slower than PPU, the interface registers read/write should be processed only on ri_ncs_in falling edges
检索自“https://acm.sjtu.edu.cn/w/index.php?title=PPCA_2018&oldid=3617”