• 理解Memory Order

    经典计算机指令的先后顺序往往也意味着逻辑关系,我们总是会直觉性的认为程序指令是从上到下一个个执行的。虽然这种直觉在很多场景下是没有问题的,但真相不止于此。如果你对memory order这个概念还不是太了解,下面这个test应该会带来一点“惊喜” ^_^

    // 代码段1
    // store-buffering校验
    P0(int x0, int x1)
    {
        int r2;
        WRITE_ONCE(x0, 2); r2 = READ_ONCE(x1); 
    }
    
    P1(int x0, int x1)
    {
        int r2;
        WRITE_ONCE(x1, 2); r2 = READ_ONCE(x0); 
     }
    
    exists (1:r2=0 / 0:r2=0)
    

    这个test的形象使用场景是——两个线程各自持有一个buffer,业务逻辑是写一次自己的buffer后读一下对方的buffer。P0和P1分别代表在两个处理器上跑的逻辑(刚开始x0,x1… 【查看更多】

  • LLVM IR简介

    对于LLVM这样的编译框架来说,IR是非常重要的。LLVM IR(Intermediate Representation,中间表示)连接着编译器前端和编译器后端。IR的设计很大程度体现着LLVM插件化、模块化的设计哲学,LLVM的各种pass其实都是作用在LLVM IR上的。同时IR也是一个编译器组件接口。通常情况下,设计一门新的编程语言只需要完成能够生成LLVM IR的编译器前端即可,然后就可以轻松使用LLVM的各种编译优化、JIT支持、目标代码生成等功能。

    LLVM IR的表示形式

    LLVM IR有三种形式:

    内存中的表示形式,如BasicBlock,Instruction这种cpp类;
    bitcode形式,这是一种序列化的二进制表示形式;
    LLVM汇编文件形式,这也是一种序列化的表示形式,与bitcode的区别是汇编文件是可读的、字符串的形式。
    内存中的IR模型

    内存中IR模型其实就是对应LLVM实现… 【查看更多】

  • 读《传习录》之【答罗整庵少宰书】

    前记:最近读到这篇文章,实在是非常精彩,因此记录一下。

    文章的背景应该是罗整庵和王阳明通信,罗质疑了王阳明的一些观点,王阳明为此做了一些回应。在看这篇文章之前,我并不知道罗整庵。查了下才知道,也是一位非常厉害的人。大概是在当时的思想圈里可以和王阳明分庭抗礼的人物。而且从王阳明的行文语气来看,可以猜测罗当时的地位(政治地位或者学术地位)是高于王的。两位都是明朝杰出的哲学家,但他们的思想却并不一致。这也是为什么我会觉得这封信非常有看点。

    1. “见道固难,而体道尤难。道诚未易明,而学诚不可不讲。恐未可安于听见而遂以为极也。”这个质疑其实挺直接的,可能罗认为王比较固执己见。
      对此,王阳明首先表达了感激之情,他说他提出自己的学说以来,常常被人嘲讽、辱骂或者不屑一顾。但是为他着想、提出建设性意见的人却非常少。
      然后,王阳明表示自己并没有那么狂妄,并说他
    【查看更多】
  • [量子计算]Shor算法

    秀尔算法(Shor's algorithm)是一种非常著名的量子算法,甚至可以说是量子计算的一块金字招牌了。Shor's algorithm可以在多项式时间内完成大整数质因数分解。所以Shor's algorithm从诞生之时,就和以RSA算法为根基的加密技术形成了不可调和的矛盾。2001年,IBM的研究小组使用Shor's algorithm完成了15 = 3×5这个整数分解运算 。时至今日,快20年过去了,量子计算机没有摧毁RSA。未来这一天来临的时候,希望我们已经准备好了。下图是,经典大数分解和秀尔算法的复杂度对比。

    Shor算法的整体流程

    完整的Shor算法是需要经典计算机和量子计算机协作完成的。其中量子计算机实现一个周期查找的函数,经典计算机负责整个算法流程的控制,以及调用量子算法。

    首先、还是表达一下Shor's algorithm的问题描述:给定一个合成数N… 【查看更多】

  • [量子计算]量子搜索Grover算法

    搜索算法是最常用的一类算法了,然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下,算法复杂度为\Omicron(N)N为数据规模。而量子计算机中存在着量子搜索算法,也称为Grover's算法,它的时间复杂度是\Omicron(\sqrt N)。听起来似乎提升不是非常大,然而在数据规模较大的情况下,量子搜索算法的优越性还是非常惊人的。例如,用Grover算法破解通用的56位加密标准(DES),只需要2^{28} \approx2.68 * 10^{8}步,而经典算法则需要2^{55} \approx3.6 * 10^{16}。如果每秒钟计算十亿次,则经典计算需要11年,而量子算法则只需要3秒钟【参考北大物理学院讲义】。

    1、 Grover算法理论基础

    Grover's算法的基本思路其实非常容易理解,而且存在非常直观的可视化解释(这一点是非常棒的!)。Grover… 【查看更多】

  • [量子计算]相位估计算法

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    量子相位估计算法

    量子相位估计算法(Quantom Phase Estimation)也称作量子特征值估计算法,是一个比较基本的算法。它的作用直观说来就是来估计一个酉变换的特征值。由于酉矩阵拥有一个性质:酉矩阵的特征值都是模为1的复数。所以对酉矩阵而言,其特征值和相位基本是对等的(因为模长已经确定了)。

    量子傅里叶变换

    在量子相位估计算法中,需要使用到量子傅里叶反变换。因此,我们简单了解一下量子傅里叶变换的相关知识。经典的离散傅里叶变换作用于一个复向量(x_{0}, x_{1},\cdots,x_{N-1}),并把它映射到另一个向量(y_{0}, y_{1},\cdots,y_{N-1}),其映射关系如下:

    y_{k}=\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} {x_{j}e^{-2\pi ijk/N}}【查看更多】

  • [量子计算] Deutsch-Jozsa算法原理与实现

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    写在前面

    学习量子力学是几年前立的Flag了,一直没有真正投入时间。主要的原因还是“要吃饭”,而且一些层出不穷的新技术也有点迷惑了我。不过本质上还是自己科学品味太差,二来加上意志力不够坚定。目前已经花了一段时间学量子力学、量子信息,写在这里权当做笔记吧!

    Deutsch-Jozsa算法问题

    Deutsch-Jozsa是一个简单的量子算法例子。虽然从实用角度讲,这个算法意义不大,但是却能很好的体现量子计算的优越性。首先是问题的描述:

    考虑一个黑盒子,我们称为oracle。它可以计算一个比特的布尔函数。每做一次计算,我们就称为是
    对oracle的一次查询。对于这个函数,存在以下四种可能:

    输入 0 1 0 1
    输出 1 0 0 1

    第(1,4)列或者(2,3)列组合而成的情况,我们称oracle为常数函数;第(1,2)列,或者(3,4)列… 【查看更多】

  • LQR与汽车横向动力学

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    LQR (linear quadratic regulator)即线性二次型调节器,这是一个非常常见的控制学科名词。以前学习《现代控制理论》的时候就有接触了,但由于最优控制这部分东西没有作为重点,所以没太掌握。但是自己心里知道《最优控制》是非常重要的,前面看强化学习Model Base部分的时候也同时买了本胡寿松版的《最优控制》。

    从个人的学习过程来看,LQR还是挺多种情况的。不少人(甚至是一些书籍的作者)都没把LQR的各种情况搞清楚。首先,LQR有离散形式和连续形式。一… 【查看更多】

  • ROS之激光雷达

    激光雷达已经成为机器人标配了,ROS作为通用机器人系统也支持激光雷达数据。激光雷达产生的数据类型是sensor_msgs/LaserScansensor_msgs/PointCloud,或者是新的sensor_msgs/PointCloud2。对于我手头的这台Turtlebot3而言,LDS设备的数据类型是sensor_msgs/LaserScan。ROS中的传感器数据非常多,但是这些数据流常常需要同步,所以ROS定义了一个通用的数据头,各种数据都会带上这个header

    ROS header的数据结构

    类型Header包括多个字段。字段seq对应一个标识符,随着消息被发布,它会自动增加。字段stamp存储与数据相关联的时间信息。以激光扫描为例,stamp可能对应每次扫描开始的时间。字段frame_id存储与数据相关联的tf帧【查看更多】

  • 强化学习之Policy Gradient笔记

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    Policy Gradient方法是强化学习中非常重要的方法。不同于基于最优价值的算法,Policy Gradient算法更着眼于算法的长期回报。策略梯度根据目标函数的梯度方向去寻找最优策略。策略梯度算法中,整个回合结束之后才会进行学习,所以策略梯度算法对全局过程有更好的把握。DeepMind的David Silver在深度学习讲座中这样评价基于策略的方法:
    Policy Based强化学习方法优点:
    - 收敛性好
    - 在高维和连续问题中比较有效
    - 能学习随机策略

    其缺点有:
    - 容易陷入局部最优
    - 评价一个策略比较低效

    基本理论

    从理论上讲,其实策略梯度其实是更容易理解的一种方法,毕竟我们对梯度下降再… 【查看更多】