plutolove’s diary

I love three things in this world, the sun, the moon and you. The sun for the day, the moon for the night, and you forever。

CUDA MatMul优化

测试环境5070Ti显卡，显存带宽896 GB/s，理论算力38.6 TFLOPS(fp32).

基线

__global__ void naiveSgemm(float* __restrict__ a, float* __restrict__ b,
                           float* __restrict__ c, const int M, const int N,
                           const int K) {
  int x = blockIdx.x * blockDim.x + threadIdx.x;
  int y = blockIdx.y * blockDim.y + threadIdx.y;
  // a -> M * K
  // b -> K * N
  // c -> M * N
  if (x < M && y < N) {
    float sum = 0.0;
    for (int k = 0; k < K; k++) {
      sum += a[x * K + k] * b[k * N + y];
    }
    c[x * N + y] = sum;
  }
}

naive:
    M=1024, N=1024, K=1024, time=0.00590492831543088 0.00590492831543088 0.00590492831543088, AVG Performance=338.70013201914054 Gflops
    M=1536, N=1536, K=1536, time=0.021052608266472816 0.021052608266472816 0.021052608266472816, AVG Performance=320.6253550420954 Gflops
    M=2048, N=2048, K=2048, time=0.04970364645123482 0.04970364645123482 0.04970364645123482, AVG Performance=321.90797139396807 Gflops
    M=3072, N=3072, K=3072, time=0.16739998757839203 0.16739998757839203 0.16739998757839203, AVG Performance=322.58066909779336 Gflops
    M=4096, N=4096, K=4096, time=0.39506909251213074 0.39506909251213074 0.39506909251213074, AVG Performance=323.99396061606546 Gflops
Read more

Clash 配置

  • 安装clash
sudo pacman -S clash
  • 配置文件,external-ui需要单独安装
port: 7890
socks-port: 7891
redir-port: 7892
mixed-port: 7893
allow-lan: false
mode: Rule
log-level: info
ipv6: false


external-controller: 0.0.0.0:9090

external-ui: dashboard

clash

  • 开机自启
sudo vim /etc/systemd/system/clash.service
[Unit]
Description=Clash daemon, A rule-based proxy in Go.
After=network.target

[Service]
Type=simple
Restart=always
ExecStart=/usr/bin/clash -d /etc/clash

[Install]
WantedBy=multi-user.target
sudo systemctl enable clash
sudo systemctl start clash

C++ 模板类型推导

C++

以下列代码为例子，当调用func(expr)时，编译器会自动推导出来T的类型和ParamType的类型，模板类型推导分为一下三种类型：

template<typename T>
void func(ParamType p);
  • 当ParamType是指针或者引用类型，并且不是通用引用类型 ，如果expr的类型是引用类型，丢掉其引用类型。然后用expr的类型去匹配ParamType以确定T的真实类型，例如：
template<typename T>
void func(T& p);

int x = 0;
const int cx = x;
const int& rx = x;

f(x);   //ParamType 为 int&, T 为 int
f(cx);  //ParamType 为 const int&, T 为 const int
f(rx);  //ParamType 为 const int&, T 为 const int
  • ParamType是通用引用类型，如果expr是一个lvalue，T会被推断为对应expr裸类型的左值引用，而根据引用折叠规则，ParamType也被推断为左值引用，如果expr是一个rvalue，情况1生效，即expr会被推断为对应的裸类型，而ParamType将会是裸类型对应的右值引用类型，例如：

引用折叠规则：

  • 到右值引用的右值引用折叠成右值引用
  • 其他所有情况折叠左值引用
template<typename T>
void func(T&& p);

int x = 0;
const int cx = x;
const int& rx = x;

f(x);       //x 为左值，ParamType 为 int&，T 为 int&
f(cx);      //cx 为左值，ParamType 为 const int&，T 为 const int&
f(rx);      //rx 为左值，ParamType 为 const int&，T 为 const int&
f(0);       //0 为右值，ParamType 为 int&&, T 为 int
  • ParamType既不是指针也不是引用，如果expr的类型中含有引用，const，volatile，则舍弃这些，然后用expr的裸类型去匹配T

Manjaro CUDA 

# 独显性能
optirun glxgears -info

# 打开nvida面板
optirun -b none nvidia-settings -c :8

# 不依赖Bumblebee来使用CUDA
sudo tee /proc/acpi/bbswitch <<< 'ON'

# 使用完CUDA 停止NVIDIA显卡
sudo rmmod nvidia_uvm nvidia && sudo tee /proc/acpi/bbswitch <<< OFF

inxi -G # 查看显卡情况
optirun nvidia-smi # 查看CPU情况

#安装cudnn
sudo cp *.h /usr/local/cuda/include/
sudo cp cudnn/lib/* /usr/local/cuda/lib/
sudo cp cudnn/lib/* /usr/local/cuda/lib64/
sudo chmod a+r /usr/local/cuda/include/cudnn.h

Kickstart Practice Round 2018 Problem Problem B. Googol String

题意

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:

switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011". reverse: The string is reversed. For example, "100" becomes "001". Consider this infinite sequence of 0/1 strings:

Read more

hiho-[Offer收割]编程练习赛65-题目4 : 解方程

hiho

题目链接:https://hihocoder.com/problemset/problem/1771

题意

设 f(n) 表示 n 的每一位数字的平方之和，求 [a,b] 中有几个 n 满足 k × f(n)=n (1 ≤ k, a, b ≤ 1018，且a ≤ b)

解法

由于f(n)表示每一位数字的平方之和，那么f(n)的范围最大不超过18*9*9，那么只需要枚举f(n)，反推出来n并判断即可。

Read more

hiho-[Offer收割]编程练习赛65-题目2 : 最长子段

hiho

题目链接:https://hihocoder.com/problemset/problem/1769

题意

给定一个数组a[1..n]，你需要选一个尽可能长的非空连续子段，使得这个子段的和小于等于给定的一个数 S.

解法

sum[i]数组维护前缀和，mas[i]数组维护以i结尾的最大的sum[i]+S：mas[i] = max(sum[i] + s, mas[i-1])
遍历所有的sum[i]，并在mas[0]到mas[i]中lower_bound查找，假设查找结果下表为index，由于mas[index]为最大的sum[index]+S，且大于等于sum[i]，那么可以的出sum[i] - mas[index] <= 0，及就是sum[i] - sum[index] <= S，且最大。

Read more

RTree index speed up Range query in SparkSQL

SparkSQL

本文接着Add Range Query on Spark DataSet继续，上一篇只是添加了基本的Range操作，为了加速执行，本文将在RDD上实现一个RTree Index来加速执行Range和Knn操作，全部代码在Github。实现之后的例子如下：

import org.apache.spark.sql.SparkSession
import scala.util.Random
object Main {
  case class PointData(x: Double, y: Double, z: Double, other: String)
  def main(args: Array[String]): Unit = {
    val sparkSession = SparkSession
      .builder()
      .master("local[4]")
      .appName("SparkSession")
      .getOrCreate()
    import sparkSession.implicits._
    var points = Seq[PointData]()
    for(i <- 0 until 3000) {
      points = points :+ PointData(Random.nextInt()%30, Random.nextInt()%30, Random.nextInt()%30, "point: "+i.toString)
    }
    val pointsList = points.toDS()
    pointsList.createIndex("rtree", "RtreeForData",  Array("x", "y") )
    pointsList.range(Array("x", "y"), Array(0, 0), Array(10, 10)).show()
    pointsList.knn(Array("x", "y"),Array(1.0, 1.0),4).show(4)
}
Read more