Volador235's blog

Welcome to my blog!

xv6 项目安装

在课程仓库的 INSTALL-xv6.md 中,仅仅编写了 MacOS 下的实验初始化方法,接下来是简单的 Linux 系统初始化方法

Linux

项目仓库克隆

使用 git clone https://github.com/mit-pdos/xv6-rsicv 进行项目克隆(我们使用 rsicv 架构版本,而非课程仓库中MacOS环境下的x86架构版本,接下来的所有实验操作都在此版本上进行)

阅读全文 »

psort 程序设计

项目文件结构

1
2
3
4
5
6
7
8
9
10
11
12
concurrency-sort/
├── Makefile # 构建文件
├── psort.md # 程序设计文档
├── README-zh.md # 项目说明
│
├── Record.h # 记录类型定义
├── psort_utils.h/.c # 内存文件映射 mfilemap
├── test_utils.h # 测试工具(随机文件生成、排序校验)
├── thread_pool.h/.c # 通用线程池
│
├── psort.h # 排序组 & 快速排序 & 线性归并
└── psort.c # 主程序 & 最小堆 k 路归并

可用例程

  • get_nprocs()
  • get_nprocs_conf()
  • mmap()
  • fsync()
  • read()
  • fread()

程序要求

  • 并行排序接收两个命令行参数
    • input
    • output
1
prompt> ./psort input output
  • 输入文件格式

    • record: key 4byte | value 96byte
  • 程序操作

    • 将所有记录读入内存,对记录进行排序,随后将其写入输出文件
    • 在完成之前,通过调用 fsync() 对输出文件进行强制写入
    • 可以假设为一次性排序
阅读全文 »

MapReduce 程序设计

原始论文


实验目标

  • 学习 MapReduce 范式的通用特性
  • 使用线程和相关函数实现一个正确且高效的 MapReduce 框架
  • 获得更多编写并发代码的经验

MapReduce框架总体思路

用户只需要定义 Map() 与 Reduce() 函数,交由框架处理该函数指针即可

  • Map(): 接受一个输入对,并产生一组中间键值对。
  • Reduce(): MapReduce库 将具有相同中间键K的中间值分组在一起,传入该函数
    • 接受一个中间键K和该键的一组值。将这些值进行合并为更小的集合
    • 通常,每次对 Reduce() 的调用产生零个或一个输出值
    • 中间值通过迭代器提供给用户的reduce函数

MapReduce 可将许多不同类型的相关计算映射到该框架上。
并且多个 mapper 可以同时运行,多个 reducer 也可以同时运行。
用户不必亲自操作编写并行化程序,只需要编写 Map() 与 Reduce() 函数,并交由该框架提供的相关基础设施即可。

阅读全文 »

GNU Compiler Collection

参考手册

本地手册

  • man gcc GCC手册
  • man g++ 通常指向gcc手册
  • info gcc 更结构化的Info格式文档

内置帮助

  • gcc –help gcc帮助
  • gcc –help=common 常用选项帮助
  • gcc –help=warnings 只看警告相关的选项
  • gcc –help=optimizers 优化选项
  • gcc -v –help 显示更详细的内部选项

官方在线文档

  • GCC在线手册: https://gcc.gnu.org/onlinedocs/
  • GCC命令行选项索引: Option Index
阅读全文 »

该实验指导文档在实验编写完成后进行了修缮与逆向更新
更贴合实际的项目进度

MapReduce 实验指导

实验分析

本项目是 OSTEP(Operating Systems: Three Easy Pieces) 的并发 MapReduce 实验。目标是实现一个单机多线程简化版 MapReduce 框架,核心是实现 mapreduce.h 中声明的函数并设计线程安全的中心数据结构。


1. 理解数据流

整个框架的数据流是:

1
2
3
4
5
6
argv[1..n] 文件列表
→ Mapper 线程池 (num_mappers 个线程) → 调用用户的 Map()
→ Map() 内部调用 MR_Emit(key, value) 发射中间数据
→ 中间数据按 Partitioner 分区 → MR_Emit 内部完成 key 去重与 value 聚合
→ map 全部完成后,每个分区按 key 升序排序
→ Reducer 线程池 (num_reducers 个线程) → 每个唯一 key 调用一次 Reduce()

在写代码之前,建议把这条数据流画在纸上,标注每一步的输入和输出。这是理解后续所有实现细节的基础。

阅读全文 »

MapReduce: 大规模集群上的简化数据处理

  • 原始论文

摘要

用户侧

  • map 函数:处理键值对,生成一组中间键值对
  • reduce 函数:合并与同一中间键关联的所有中间值

特性

  1. 自动并行化,适于在大型机器集群上执行。
  2. 运行时系统负责处理输入数据的分区、跨机器集合调度程序执行、处理机器故障以及管理所需机器间通信。提供了一种方法,封装了分布式系统的复杂性。
  3. 具有高扩展性,可以适配多种分布式程序任务

方案背景

MapReduce框架的出现,是为了解决,大量数据如何在大型分布式系统上实现并行化计算、分布数据和故障处理等,复杂的并发细节(该问题导致原来设计的简单计算任务代码,为了满足分布式系统的并发需求,而增加了大量的并发复杂性)

MapReduce在计算任务与分布式系统之间设计了一种新的抽象,将简单计算与复杂并发细节相分离。

MapReduce库的抽象设计受到Lisp及许多函数式语言中的 map 与 reduce 原语的启发。对输入的每个输入逻辑应用 map 操作,计算一组中间键值对,对共享相同键的值应用 reduce 操作,以适当的合并派生数据。将函数式的 map 与 reduce 的实现交由用户制定,库只需要提供并行化方法,使用户轻松实现程序并行化。该库将重新执行作为容错的主要机制。

map 与 reduce

  • map 映射
  • reduce 归约
阅读全文 »

SFML cloth simulation

使用 粒子弹簧模型 进行 运动学模拟

理论公式

位置 Verlet 积分

选用 Verlet 位置更新公式

Verlet 积分:

公式推导

泰勒展开法

更新质点状态

  1. 假设粒子运动状态

    • 粒子的位置为
    • 速度为
    • 加速度为
    • 以上三项公式都仅依赖于 位置
  2. 取时间步长为 ,分别在 时刻前后作三阶泰勒展开

  3. 将上述两式相加

    • 将上式进行整理 得到上述公式
    • 可见,该式表示,当前的位置仅依赖于上一时刻的位置,以及当前的加速度
    • 若需要速度,可是使用 中心差分估计
阅读全文 »
0%