Stock Selection via Spatiotemporal Hypergraph Attention Network – A Learning to Rank Approach

论文原址:https://www.aaai.org/AAAI21Papers/AAAI-7907.SawhneyR.pdf

这几年研究把深度学习应用到量化交易和传统投资决策的论文并不少,但都有2个问题:

  1. They do not directly optimize the target of investment in terms of profit
  2. and treat each stock as independent from the others, ignoring the rich signals between related stocks’ temporal price movemen

为了解决这些问题,作者提出了一种叫 STHAN-SR 的超图神经网络。并通过对美3大交易所最近6年的数据,证明这个网络在当前所有股票预测算法里面是最优的

Introduction

美股市场,68万亿,19年

forecasting:预测

highly volatile and non-stationary nature – 股票市场具有很强的波动性

synergy 协同

当前主流的股票预测算法,最大的弊端就是不以投资收益为优化目标。因为这些算法,要么是基于回归来预测价格,要么基于分类来做交易决策,这种分类和回归的优化目标是为了提高股票价格走向的准确性或最小化预测股票收益的误差,而不一定是为了直接利润

(有什么不一样吗??一脸懵比)

0

第二个弊端就是不考虑股票之间的相关性,总是把这些股票作为独立的个体来分析,或者使用一个过于简化的股票市场模型,一个由单个股票之间的成对关系组成的图表,但在现实中,这与真正的市场是相反的


dCat – Dynamic Cache Management for Efficient Performance-sensitive Infrastructure-as-a-Service

核心前提:只要独占 cache size 足够大,业务的性能是可以得到保证的
we can conclude that whether CAT can provide perfor mance isolation between workloads is highly dependent on the size of the dedicated cache

思路:基于CPI的动态反馈,来动态调整每个容器的独占 cache 和共享 cache 容量,达到每个容器都可以得到很好的性能

难点:预测 wss(业务真正需要的cache size)。这里面有一个容量失效和冲突失效的问题,冲突失效和容量失效是 有一定的overlap的,冲突失效是因为多条cache数据映射到同一个cache line上,导致的miss,这个问题会导致wss难以预估。这个问题没有什么太好的思路,所以dCat的思路是基于feedback来动态扩大cache size

dCat 的状态机是这样的:
简单来说,是一个实时feedback的过程
Reclaim:初始状态
Recevier:减少cache退化,增加cache会提升
keeper:减少cache退化,增加cache不提升
Donor:减少cache不退化,增加cache不提升
Streaming:增加cache不断提升

系统流程:

备注:

  1. baseline是基准性能,但是每个阶段,都有不同的 baseline,会动态变化 Baseline performance is only defined for a specifi workload phase, so it has to be determined again at every phase change.
  2. Categonize workloads,就是识别容器的状态,对应到上面的几个状态机上,Reciver、keeper、Doner

问题:

  1. 论文中CAT隔离,使用的是qpos,qpos是CAT的前身,只支持core级别的cache隔离,也就是cache隔离相当于是通过绑核实现的

Software-defined far memory in warehouse-scale computers

论文重点

  • 采用软件zswap的方式进行cold memory数据压缩
  • google的业务有32%的memory数据是cold memory,其中20%的数据是可压缩的,压缩效率中位数为3倍,那么TCO有4.2%的收益
  • 该压缩策略保证了SLA不受影响:通过cold memory和promotion rate的模型保证
  • 压缩解压缩的开销不大,完全可以接受
  • 使用ML进行autotuner

1 introduction

问题:
  • 随着资源的scaling,一个资源瓶颈会影响整个scaling的TCO。
  • DRAM成为scaling的瓶颈,memory的TCO减少逐渐放缓
  • 随着大数据workload的普及,主流的in-memory computing的方式加速了DRAM的需求
方向:far memory(介于DRAM和DISK之间的存储)
far memroy需要解决的问题:
  • 不影响应用的性能
  • 应用数量多且种类多样,不能对每个应用单独优化(不现实),需要对业务透明且robust的机制,有效使用Far memory
  • 动态的cold数据行为:业务的数据冷热是会变化的,比如不同该时间段

 


Concurrency management in BPF

eBPF 对并发编程的支持是非常弱的

有一些讨论:

  1. https://lists.iovisor.org/g/iovisor-dev/topic/bpf_concurrency/74407447
  2. https://lwn.net/Articles/779120/

但是你甚至在 eBPF 的官方文档 https://github.com/iovisor/bcc/blob/master/docs/reference_guide.md 里面几乎找不到任何关于并发的描述,除了 map.atomic_increment() 接口

但是这个借口也很奇怪。为了突出这个接口是原子的,线程安全的,难道其他接口就不是了吗?但好像又不是,因为 eBPF 里有大量的示例,并没有对 map 做特殊的并发控制,所以理论上可以认为,其他大部分 map 操作接口,也是线程安全的

线程安全验证

测试代码如下:

// calculate latency
int trace_run(struct pt_regs *ctx, struct task_struct *prev)
{
    u32 pid = bpf_get_current_pid_tgid();
    u64 *tsp;
    if (pid <= 1) {
        return 0;
    }
    
    pid = 10000; 
    u64 ts = bpf_ktime_get_ns();
    start.update(&pid, &ts);
   
#define __OP__ == 
    tsp = start.lookup(&pid); if (tsp __OP__ 0) { dist.increment(bpf_log2l(1)); }
    tsp = start.lookup(&pid); if (tsp __OP__ 0) { dist.increment(bpf_log2l(1)); }
    /** 重复N次 **/
    tsp = start.lookup(&pid); if (tsp __OP__ 0) { dist.increment(bpf_log2l(1)); }
    tsp = start.lookup(&pid); if (tsp __OP__ 0) { dist.increment(bpf_log2l(1)); }
    
    start.delete(&pid);
    return 0;
}

这段代码,修改自 bbc 工具集自带的 runqlat.py

这段代码实际上是在构造一个冲突场景,来验证 trace_run 到底是并行执行还是串行执行的。代码的逻辑是在一个超高频触发的钩子(调度器进行上下文切换)函数里,先在 map 里插入一个固定key(pid)的元素,然后查询 N 次,每次查询如果 key 不存在,计数器就 +1,最后把 key 从 map 里面删除掉,如果:

  1. trance_run 是串行的,那么技术器永远都是 0,因为在一个串行执行的逻辑里,插入元素后,不管查询多少次,元素必然是存在的
  2. 如果 trace_run 是并行的,那么就存在一个条件,一定有一个 cpu,在另外一个 cpu 查询 key 是否存在的时候,执行到了函数结束的地方,把 key 从 map 里面删掉了

事实证明,trace_run 是并行执行的,并且中间 lookup 的次数越多,冲突的概率就越大


cgroup 内存管理之 mlock 内存

我们在使用容器的过程中,可能会遇到一个问题,容器利用率很低,但是经常发生 oom,这是什么情况?

很可能是业务使用了一些不可回收的 page cache,其中最主要的应该就是 mlock

1. mlock 的背景

mlock 的作用就是防止页面被换出到 swap 分区,或者 page cache 被内核回收

由于线上服务器,基本默认都会关闭 swap 分区,所以这种情况暂不讨论,防止 page cache 被内核回首是主要作用

什么样的 page 需要 mlock?

1)通过 mmap 方式映射到内存中的 page cache,比如一些关键的索引数据,需要经常访问,那就得 mlock 住,否则 pgmajfault 带来的性能抖动是很大的

2)程序自身依赖的一些 so 动态链接库,由于内核的 page cache 回收算法,并不感知 page 具体是普通的文件 cache,还是 so 动态链接库,所以当容器内存不足时,内核通过一些粗略的回收算法回收 page cache,一旦把 so 的缓存页回收掉了,程序在调用相关函数时,会出现严重的性能抖动

因此,通过 mlock,显式的把一些关键的不希望被回收的 page cache 锁定起来,达到保证业务性能的目的

2. mlock 的内核实现

mlock 相关的系统调用可以参考:https://linux.die.net/man/2/mlock

2.1. unevictable 内存

cgroup 的 memory.stat 接口,包含一个容器内存使用的详细信息

cat /cgroups/v2/matrix/memory.stat 
anon 200723943424
file 158665015296
kernel_stack 0
slab 0
sock 229249024
shmem 4258582528
file_mapped 48234749952
file_dirty 8605696
file_writeback 0
inactive_anon 4258234368
active_anon 200570675200
inactive_file 73935654912
active_file 40680521728
unevictable 39942680576

其中 unevictable 表示不剔除的 page cache,mlock 属于 unevictable 的一部分,除此之外,unevictable 还有一些其他内存


cgroup 内存管理之 tmpfs

本文内核代码版本:https://elixir.bootlin.com/linux/v4.14.281/source/mm/shmem.c

1. tmpfs 内存简介

tmpfs 文件系统是 pod 中常见的一种“存储”介质,也叫 ram disk,都是一个东西

tmpfs 的特殊的地方在于:

  1. 首先它是个文件系统
  2. 但是它的文件数据是完全存放在内存里面的,不在磁盘上

所以要讲 tmpfs 的话,就得把这两部分都讲清楚,一个是文件系统的实现,一个是底层“持久化”层内存的管理

通常应用程序之间会通过 tmpfs 文件系统来实现高效的数据共享

/dev/shm 就是一个最典型的 tmpfs 文件系统,是操作系统为了解决大多数程序数据共享而默认挂在的一个 tmpfs

2. tmpfs 文件系统的实现

我们知道 file 是linux内核最重要的设计,一切皆文件

除了普通的文件,平时我们接触到的,unix管道、socket、proc、cgroup 等等,都是基于文件的实现

为了实现灵活可扩展的文件系统架构,Linux设计了 virtual file system 抽象层,简称 vfs,对用户台程序屏蔽了所有具体的底层文件系统的实现细节,提供统一的文件系统接口

2.1. virtual file system 接口定义

https://www.kernel.org/doc/html/latest/filesystems/vfs.html

vfs 属于一个专题,我们这里不讲那么复杂,有时间可以专门展开讲

vfs 定义了文件系统实现最关键的2个接口:

  1. 一个是 struct file_operations:文件读写的接口
  2. 一个是 struct inode_operations:inode操作接口

inode_opertions 定义如下:

struct inode_operations {
    int (*create)(struct user_namespace*, struct inode*, struct dentry*, umode_t, bool);
    int (*symlink)(struct user_namespace*, struct inode*, struct dentry*, const char*);
    int (*mkdir)(struct user_namespace*, struct inode*, struct dentry*, umode_t);
    int (*rmdir)(struct inode*, struct dentry*); /* 省略一万字 */
};

是不是很熟悉?

file_operations 的定义如下:

struct file_operations {
    int (*open)(struct inode*, struct file*);
    loff_t (*llseek)(struct file*, loff_t, int);
    ssize_t (*read)(struct file*, char __user*, size_t, loff_t*);
    ssize_t (*write)(struct file*, const char __user*, size_t, loff_t*); /* 省略一万字 */
};

是不是也很熟悉?

内核 tmpfs 文件系统的源码:mm/shmem.c

tmpfs 其实并没有实现 vfs 中的所有接口,主要原因是因为由于绝大部分的 file system 底层实现其实都是一样的,没区别,所以内核为了简化文件系统的开发,把这些通用的实现都抽象出来,变成 generic_file_read/write 之类的通用实现

static const struct file_operations shmem_file_operations = { /* 普通文件的读、写、seek、fsync */ .mmap = shmem_mmap, .get_unmapped_area = shmem_get_unmapped_area, #ifdef CONFIG_TMPFS .llseek = shmem_file_llseek, .read_iter = shmem_file_read_iter, .write_iter = generic_file_write_iter, .fsync = noop_fsync, .splice_read = generic_file_splice_read, .splice_write = iter_file_splice_write, .fallocate = shmem_fallocate, #endif };
static const struct inode_operations shmem_inode_operations = { /* 这个是针对普通文件的 inode 操作 */ .getattr = shmem_getattr, .setattr = shmem_setattr, };
static const struct inode_operations shmem_dir_inode_operations = { /* 这个是针对目录的 inode 操作 */ #ifdef CONFIG_TMPFS .create = shmem_create, .lookup = simple_lookup, .link = shmem_link, .unlink = shmem_unlink, .symlink = shmem_symlink, .mkdir = shmem_mkdir, .rmdir = shmem_rmdir, .mknod = shmem_mknod, .rename = shmem_rename2, .tmpfile = shmem_tmpfile, #endif };


记一则 cfs 硬限引发的 cgroup_mutex 死锁

cgroup_mutex 是内核实现 cgroup 子系统而重度依赖的一把全局锁,这把全局锁在很多场景下会带来非常多的性能问题。具体这里不展开讲了,google 一下 cgroup_mutex deadlock,可以看到一堆 bugs report

最近线上恰好遇到一次机器死机的场景,后来分析发现和 cgroup_mutex 死锁有关(严格来说不叫死锁,叫夯死更合适一些),以此记录分析过程

1. 现象

机器存在大量的 D 进程,监控发现系统负载缓慢持续增高,应该是由于D进程持续不断地堆积,导致负载越来越高

所有与 cgroup_mutex 打交道的地方,都会卡死,比如简单来说 cat /proc/self/cgroup 会立即进入夯死状态,进程无法 kill -9 杀掉

我们通过一些艰难的内核栈跟踪,终于捕捉到了内核临死前的锁持有的状态(此处省略掉1万字跟踪过程)

2. 内核栈分析

读过内核源码或者了解内核原理的应该知道,vfs_write 是内核文件系统的抽象层。vfs_write 接着调用 cgroup_file_write,这个说明当前进程正在写 cgroup 文件系统,然后在写过程中,陷入 synchronize_sched,进程被换出,然后应该是一直卡在这里了。

但是真正导致系统死机的,并不是 synchronize_sched 这个地方,二是一个很复杂的链,触发场景:

  1. 进程持有 cgroup_mutex
  2. 进程尝试获取其他锁,或者进入睡眠态
  3. 进程 cfs 时间片被 throt,导致进程无法重新获得 cpu 的控制权,cgroup_mutex 无法释放

cgroup_mutex 是一把极大的锁,几乎任何 cgroup 操作都会涉及到这把锁的操作。在我们这个场景里,进程持有 cgroup_mutex 之后陷入 __wait_rcu,其他进程在尝试持有 cgroup_mutex 的时候几乎全部都夯住了


CTS: An operating system CPU scheduler to mitigate tail latency for latency-sensitive multi-threaded applications

论文原址:https://www.cs.jhu.edu/~erfan/files/cts.pdf

cts 提出了一种优化长尾延迟的方法,通过改进 linux 内核默认的 cfs 调度器,引入线程调度机制

论文的一些要点:

  • It has been proven that FCFS scheduling of threads leads to lower tail latency
  • Experiments show that CFS policies lead to LCFS scheduling, aggravating tail latency
  • CTS policies ensure FCFS thread scheduling, which yields lower tail latency.
  • CTS enforces our policies while maintaining the key features of the Linux scheduler
  • Experimental results show that CTS significantly outperforms the Linux scheduler

延迟敏感型的程序,通常有两种进程模型,一种是 thread-driven,另一种是 event-driven。前者很容易理解,起1个线程来服务一个请求,模型很简单。后者相对复杂一些,比如 libev,libevent 都是用来实现 event-driven 架构的基础库,通过 io 多路复用技术,将 io 线程和 worker 线程分离,io 线程专注数据转发,worker 线程专注业务逻辑处理

但是这个 io 线程很关键,如果数据 ready,但是得不到处理,会导致严重的长尾延迟。io 密集型的程序瓶颈不在 cpu,而是 io,CPU 上的时间片消耗是非常小的,远小于1ms,因而这种进程理论上应该优先获得响应


ImageNet Classification with Deep Convolutional Neural Networks

论文原址:https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf

无论是AI、深度学习,还是卷积神经网络,都不是这几年才有的概念,但确实是最近10年才流行起来。这里最主要的原因,还是要归功于AlexNet 2012年在大规模视觉识别挑战赛上取得的成功,所以才有了这篇论文

在这篇论文里面,AlexNet 提出了很多创新性的 idea,对卷积神经网络的发展影响深远,其中很多概念仍然是今天 CNN 的核心

论文的特点:

  1. AlexNet 包含许多心的不同寻常的特性,这些特性提高了神经网络的性能并减少了训练时间
  2. 提出 Dropout 解决过拟合的问题

下面我们再详细看下

不同寻常的网络特性

1. 非饱和神经元 ReLU

使用 ReLU 的四层卷积神经网络在 CIFAR-10 数据集上达到 25% 的训练误差比使用 tanh 神经元的等价网络(虚线)快 6 倍。为了使训练尽可能快,每个网络的学习率是单独选择的。没有采用任何类型的正则化。影响的大小随着网络结构的变化而变化,这一点已得到证实,但使用 ReLU 的网络都比等价的饱和神经元快几倍。

0

论文里有一片引用论文:https://www.cs.toronto.edu/~fritz/absps/reluICML.pdf

可以参考下


Visualizing and Understanding Convolutional Networks

论文原址:https://arxiv.org/pdf/1311.2901.pdf

1. 背景

我们都知道 CNN 卷积神经网络 效果好,但是一直以来都是一个黑盒,有2个关键问题:

  1. However there is no clear understanding of why they perform so wel
  2. or how they might be improved

其实包括我自己也是很困惑的,卷积神经网络有非常多。但是你看网上的资源来来回回都是在讲这些神经网络的结构。但是很少人知道为什么要把结构设计成这个样子。比如LeNet-5第一层卷积层为啥需要6个通道?为什么整个网络只需要2个卷积层,能不能更多或者更少?

为了解决这个黑盒问题,论文作者提出了一种可视化的方法,能够观测到卷积层的feature maps到底识别到了图片的什么特征,并以此反馈来改进神经网络的结构设计。最后通过这个方法,作者在ImageNet测试集上取得了非常突出的结果

2. 方法

论文的核心思想:map these activities back to the input pixel space, showing what input pattern originally caused a given activation in the feature maps

以LeNet-5这种经典的2D网络为例,正向的卷积过程一般包括几个步骤:

  1. filter
  2. relu
  3. max pooling
  4. 【optionally】local contrast operation

0