x-monthly-subscription

Discussion 4

Date & Time: April 28, 18:30 ~ 20:00

出席

赵家兴（记录），陶柯宇，陈昂，李喆昊。

议题

讨论并确保理解方差分析算法，拟为接下来的编程做分工。

讨论内容总结

方差分析算法详述

设每 t 时间有一个数据，在整个时间轴上的若干数据中：

• 设 “时间窗口 i ” 长度为 T（5秒） ，在 T 中包含的 N 个数据中做 50 次（有或无放回）抽样，样本个数为 N 的 20%。
• 对每一次抽样得到的样本 N’，求样本数据的均值 mean 和方差 var。
• 对 50 次抽样得到的 50 个样本均值 mean_i 和样本方差 var_i ，求序列 mean_i [ ] 和 序列 var_i [ ] 的均值与方差 MEANi(mean)，VARi(mean)；MEANi(var)，VARi(var)。

向更晚的时间滑动该时间窗口得到下一个时间窗口 j，并使得窗口 i 和窗口 j 有 80% 的数据重叠。同理得到均值序列 mean_j [ ] 和方差序列 var_j [ ]。

• 设 total := 0
• 对 mean_j [ ] 中的每一个元素 mean_j [ x ]，判定不等式 Abs[mean_j [ x ] - MEANi(mean)] > 5 Sqrt[VARi(mean)] 是否成立，若成立，total := total+1。
• 判定 total/50 > 1/25 是否成立，若是，则 i 窗口的结尾应做一个状态分割。若否，继续下面的计算。
• 设 total := 0
• 对 var_j [ ] 中的每一个元素 var_j [ x ]，判定不等式 Abs[var_j [ x ] - MEANi(var)] > 10 Sqrt[VARi(var)] 是否成立，若成立，total := total+1。
• 判定 total/50 > 1/100 是否成立，若是，则 i 窗口的结尾应做一个状态分割。若否，则 i 窗口与 j 窗口属于同一状态。

方差分析算法（Cpp实现）

请所有人都仔细阅读一遍整个文件的所有注释和代码！！！

ANOVA_v1.cpp

涉及到的输入文件 raw.txt

eBPF - C 代码编写与其他事项的工作分配（每个人的部分所有人都要看）

付佳伟：外部程序转换格式 + 数据包发送（五一放假结束时完成）

对于 raw.txt 中的每一行做成一个数据包（如果你觉得太过浪费，可以每2行、4行、··· 、（至多）128行做成一个数据包）。数据包中，数据段依次包括（二进制格式）：

• 该行第二列的时间戳值，以64位二进制无符号数表示
• 第三列、第四列、第五列的三个浮点数值，以64位 double 类型的二进制表示法表示（参阅 https://en.wikipedia.org/wiki/Double-precision_floating-point_format#C_and_C++ ）
• 每一行其他列的数据不管。

并向陶柯宇阐明自己数据包每一位的格式（数据包二进制从第几位到第几位是上述四个64位值）。同时实现将数据包发送到网卡上的方法。

（本要求在两周内完成）同时实现测试延迟的方式。

陶柯宇：eBPF - C编程（五一放假结束时完成）

对于有如上假定的付佳伟发来的数据包，以提取其中的四个数值（时间戳值，三个浮点数值（但浮点数以64位整数变量来存放）），并将“浮点数”转化为 ANOVA_v1.cpp 中要求的精度的整数（26位二进制数，各位权乘以 B-20 ），并计算三轴加速度平方和后存储在“数组 x 中”（使用 Array Map 实现数组 x，x 中的每个元素是54位二进制无符号整数，用unsigned long long表示）。

同时，对于应当划分状态的时间戳（对应 ANOVA_v1.cpp 中唯一的printf语句），实现向用户监视返回该时间戳值的方法。

总之，该部分任务将真正地处理（或发送）数据包，要涉及到 XDP 或其他东西对数据包的操作。

你将涉及到将如下语句转换成对数据包和数据的（循环）操作

unsigned int count=0u;
while (fgets(str,4096,stdin)!=NULL){
    sscanf(str,"%*d %llu %lf %lf %lf",&t,a,a+1,a+2);
	x[count++]=a[0]*a[0]+a[1]*a[1]+a[2]*a[2];//这里要转换成高精乘和高精加
    if (!(count>>9)) continue;//即 count<512
    window_end_time[0]=t;
	......
	break;
}
unsigned int newcount=0u;
while (fgets(str,4096,stdin)!=NULL){
    sscanf(str,"%*d %llu %lf %lf %lf",&t,a,a+1,a+2);
    //开始用新数据覆盖旧数据
    x[(count+newcount++)&((1u<<9)-1u)]=a[0]*a[0]+a[1]*a[1]+a[2]*a[2];//这里要转换成高精
    if (!(newcount>>7)) continue;//即 newcount<128
    window_end_time[1]=t;count+=newcount;count&=(1u<<9)-1u;
    ......
    if (tot_mean>4u||tot_var>1u) printf("%llu\n",window_end_time[0]);
}

陈昂：eBPF - C 编程（五一放假结束时完成）

实现如下高精度定义：

• 高精度数unsigned long long a[8]是256位无符号整数 (HignAccuracy256) ，数组中的每一位是64位无符号整数但只使用低32位（这方便我们在做高精度乘法时不溢出），从a[0]到a[7]依次是较低有效位到较高有效位。该数将替换我们在 ANOVA_v1.cpp 中的浮点数。
• 同时实现a[4]为128位无符号整数 (HignAccuracy128) 。至于64位以下的无符号整数，直接用unsigned long long表示。

实现如下高精度运算接口：要说明的是，这些函数最后都不会做成函数调用的形式，而会被粘贴进对应的代码段inline处理，故不必过分纠结 &a 这种操作。

void add_128_128(HignAccuracy128 &a, HignAccuracy128 b){
	a+=b;
}
void add_256_128mul128(HignAccuracy256 &a, HignAccuracy128 b, HignAccuracy128 c){
    a+=b*c；
}
void add_128_64mul64(HignAccuracy128 &a, unsigned long long b, unsigned long long c){
    a+=b*c;
}
void sub_256_128mul128(HignAccuracy256 &a, HignAccuracy128 b, HignAccuracy128 c){
	//assume and guarantee that a>=b*c
    a-=b*c；
}
void sub_128_64mul64(HignAccuracy128 &a, unsigned long long b, unsigned long long c){
    //assume and guarantee that a>=b*c
    a-=b*c;
}
void rs_7_128(HignAccuracy128 &a){
    a>>=7;
}
void rs_6_128(HignAccuracy128 &a){
    a>>=6;
}
void rs_6_256(HignAccuracy256 &a){
    a>>=6;
}
void compare_128_128(int &flag, HignAccuracy128 a, HignAccuracy128 b){
	flag=(a>b);
}
void sub_abs_128_128(HignAccuracy128 &c, HignAccuracy128 a, HignAccuracy128 b{
    if (a>=b) c=a-b;
    else c=b-a;
}
void rs_4_128(HignAccuracy128 &a){
    a>>=4;
}
void compare_256_256(int &flag, HignAccuracy256 a, HignAccuracy256 b){
	flag=(a>b);
}

李喆昊：eBPF - C 编程（五一放假结束时完成）

完成 ANOVA_v1.cpp 中的抽样，均值和方差计算，均值的均值、均值的方差、方差的均值、方差的方差的计算代码（或者说就是非陶柯宇涉及到的代码）。涉及到的数组访问调用array map的helper function，涉及到的高精度各种运算调用上述接口，涉及到输入输出的写一行注释跳过即可。

即要转化如下代码：

......
window_end_time[0]=t;
/*
在512个数据中抽样64次，每次抽样128个
此例使用无放回抽样，被分到这部分锅的人若觉得实现过于复杂任务过于繁重，可以采用有放回抽样，但这种简化很可能让我们的最终结题报告的时候被问的下不来台（
*/
MEANmean[0]=0.,VARmean[0]=0.,MEANvar[0]=0.,VARvar[0]=0.;//MEANmean直接用ull；VARmean用128位高精度；MEANvar用128高精度；VARvar用256位高精度
for (unsigned int i=0u;!(i>>6);++i){
    double mean=0.,var=0.;//mean用ull表示，var用128位高精度表示
    unsigned long long vis[8]={0ull};//由于512=64*8，用8个ull来表示这个“是否已抽过”的bool关系就可以
    for (unsigned int j=0u;!(j>>7);){
        unsigned int k=((unsigned int)rand())&((1u<<9)-1u);//这里的&((1<<9)-1)代表对512取模，它也可以用一次左移再一次右移实现。下面出现的这种写法都一样。
        if (vis[k>>6] & (1ull << ( k & ((1u<<6) - 1u) ) ) ) continue;
        vis[k>>6] |= 1ull << ( k & ((1u<<6) - 1u) );
        ++j;
        mean+=x[k];var+=x[k]*x[k];//mean是最多128个54位相加，直接用ull；var是54位乘54位=108位，用128位高精度
    }
    mean/=128.;//mean右移7位，直接用ull
    var/=128.;var-=mean*mean;//var用128位右移7位的运算；后一个用ull*ull返回128位高精度的操作
    MEANmean[0]+=mean;//直接用ull
    VARmean[0]+=mean*mean;//用64*64加给128位高精度
    MEANvar[0]+=var;//用128位高精度+128位高精度
    VARvar[0]+=var*var;//256位高精度+=128位高精度*128位高精度
}
MEANmean[0]/=64;MEANvar[0]/=64;//这里要转换成高精移位：分别是ull右移6位，和128位高精度右移6位
VARmean[0]/=64;VARmean[0]-=MEANmean[0]*MEANmean[0];//这里要转换成128位高精右移6位，128位高精-=64*64位ull
VARvar[0]/=64;VARvar[0]-=MEANvar[0]*MEANvar[0];//这里要转换成256位高精右移6位，256位高精度-=128位*128位高精度
......

上面是处理第一个窗口的代码；处理别的窗口并判定是否要做划分的代码也要搞，但是很类似，就不粘贴进来了。

赵家兴：eBPF - C编程（五一放假结束后的下一周结束前完成）

组长在五一假期学习 eBPF，为其他组员编程提供协助。

五一结束后，组长负责将各个人的代码整合起来，形成一个可以通过编译的版本——这包括统一变量名，将高精度调用插入进代码段，调整一些不太大的数组是否要用 Array Map 等等。该工作将在五一后的一周内完成，期间将可能要求其他组员协助做代码的更改。