x-monthly-subscription

Discussion 5

Date and Time :

2019.05.04 , Cloud discussion

出席：

组长自己来分锅

议题：

根据五一假期大家不懈努力踩出来的诸多巨坑，经与老师讨论，重新规划了算法内容；拟划分时间节点并分配任务。

算法内容：

方差分析算法 ver 2.0：

• 设一个窗口有 16 个数据，每次窗口滑动时，滑动 1 个新数据。这意味着，数据 data[ 31 : 0 ] 包含了若干窗口 data[ 15 : 0 ]，data[ 16 : 1 ]，······，data[ 31 : 16 ]。
• 这次，我们将比较两个没有数据重叠的窗口！但是其数据彼此相邻，如 data[ 15 : 0 ] 与 data[ 31 : 16 ]（后续还可能同时追加比较更远的窗口，但这里先不涉及，除非老师来改需求）
• 对于 data[ 15 : 0 ]，我们计算这 16 个数据的均值 mean 和方差 var。
• 取参数 e := 0.1（调参得到，我们不必管，这也是老师给的），计数器 tot := 0

• 对 data[ 31 : 16 ] 中的每个数据 x，判断

  x - mean

  >= e 是否成立，若成立，tot += 1

• 判定 tot/16 <= var/(e^2) 是否成立，若不成立，则在 data[ 15 : 0 ] 和 data[ 31 : 16 ] 之间划分状态。

算法 C 描述：

见 ANOVA_v2.c，请仔细阅读。

初步分锅：

考虑到 OSH 时间紧迫与数理方程考试的双重压力，本次锅除非特殊声明，请在 5 月 11 日（星期六）晚24点前完成，组长会尽量考虑到每个人的实际，安排不同的任务并尽可能减小各位的负担。如果提前做完，请提前 push 到大家对应的 code 文件夹。

总体注意事项

1. 我们可以使用栈，但是操作栈的 “offset” 必须是常数，这意味着数组下标的操作必须都是常数。
2. 跳转语句不能向前跳转，意味着循环必须全部展开。
3. 不要使用 map 数据结构和其他的 helper function。

付佳伟：数据打包与包发送（至晚在数理方程结束后的半周内完成）

对于例如 data_000001SZ.txt 这样的原始数据，打包成例如data_arranged_000001SZ.txt 的形式（每一行是一个包）。并且预留两个空间。原始数据满足不大于65535，小数点后至多3位。

具体来说：

• 每个包的数据段要包含 1+1+32 = 34 个64bit数据。
• 第一个 64bit（或更小）是 “magic number”，作用是标识出这是我们要处理的数据包。
• 第二个 64bit（或更小）是 “tag number”，当前的想法是：初始为0，处理过后划分为1，不划分为2。
• 第 3 到 34 个 64bit 是 “data area”，每个 64bit 是 double 格式的二进制浮点数，对应着“算法内容”部分所讲到的 32 个数据。
• 一个包就是一个处理过程和一个划分判定所需要的全部数据，后续如果会将需求复杂化，这个原则也不会变。

陶柯宇：包解析，提取数据

对于上文付佳伟发来的数据包格式，做 “magic number” 判定（不匹配则丢弃），“tag number” 判定（0则处理，非0则丢弃）。

随后，将后面的 32 个 double 二进制（都是正数）先存入一个 ull 变量数组 unsigned long long data[32] 内。

同时写一段独立的代码，用来修改 “tag number” 并返回 XDP_TX，即无论划不划分状态，都修改 “tag number” 并将修改后的数据包重定向回网卡输入（即使它还会在下一次处理被丢弃，但实现一下以备后续需求的变化）。

陈昂：浮点—>整数格式转化

对于上文陶柯宇生成好的数组 unsigned long long data[32]，通过位运算等一系列操作，将其转化为存入 ull 的 26 位无符号整数，其中最高位的位权是 2^15，最低位 2^-10。之后将其存入一个 unsigned long long x[32] 数组内。

关于 double 每一位含义，参阅 wikipedia。注意符号位是不需要的，因为我们保证了均是正数。

李喆昊：其余程序翻译

将程序的后续部分翻译成 eBPF - C 编程的格式，要注意循环的展开、数组下标的访问要是常数等等。

赵家兴：每个人的程序的整合与辅助

将在其他人写好程序之后，将其整合起来并调试直到通过编译。同时与各种信息渠道保持沟通。