基于非参数密度估计的不确定轨迹预测方法

随着大量移动设备的出现,准确和高效的轨迹预测有助于提高面向位置的应用和服务的质量和水平.针对现有方法对轨迹不确定性缺乏有效建模的问题,提出了基于非参数密度估计的不确定轨迹终点预测方法.在轨迹建模及模型训练阶段,利用非参数估计对起点与终点相同的轨迹构建基于密度分布的不确定轨迹模型;在轨迹预测阶段,将待预测轨迹视为轨迹数据流,并通过KS (Kolmogorov-Smirnov)检验方法与具有相同起点的不确定轨迹模型进行匹配,其中匹配程度最高的不确定轨迹即为预测轨迹.通过真实轨迹数据集上的实验表明,与现有各类主要轨迹预测方法相比,本方法在不同条件下的预测效率与准确性都有较明显优势.

基于滑动窗口的多核程序数据竞争硬件检测算法

数据竞争是引起多核程序发生并发错误的主要原因。针对现有基于硬件的happens-before数据竞争检测方法硬件开销大的问题,提出了一种轻量级的内存竞争硬件检测算法,该算法利用滑动窗口技术动态检测程序执行过程中发生的距离较近、更易引发并发错误的数据竞争。考虑竞争距离的大小,将并发线程片段细分为加锁并发竞争域和包含线程近期执行序列的未加锁并发竞争域,用一对交替移动的可重写滑动窗口保存未加锁并发竞争域内的内存操作指令,用一个大小可变的可重写滑动窗口保存加锁并发竞争域内的内存操作指令,当来自远程的共享访问与窗口内的内存访问发生冲突时,检测到数据竞争。在硬件实现结构中,仅为每个处理器核添加3对较小尺寸的硬件签名寄存器来保存并发竞争域内的数据地址,无需更改原有的cache一致性协议,带来的带宽开销低,能够快速地检测多核程序并发执行过程中发生的动态数据竞争,为多核程序开发和生产运行阶段的并发错误诊断提供有效的指导信息。

面向监听一致性协议的并发内存竞争记录算法

内存竞争记录是解决多核程序执行不确定性的关键技术,然而现有点到点的内存竞争记录机制带来的硬件开销大,难以应用到实际的片上多核处理器系统中.以降低点到点内存竞争记录方式的硬件开销为出发点,为采用监听一致性协议的片上多核处理器(chip multiprocessor,CMP)系统设计了基于并发记录策略的点到点内存竞争记录算法.该记录算法将两两线程间点到点的内存竞争关系扩展到所有线程,采用分布式记录方法为每个线程记录一个由内存竞争关系的一方构成的内存竞争日志;重演时采用简化的生产者消费者模型,确保了确定性重演的实现,有效降低了硬件消耗和带宽开销.在8核处理器系统中的仿真结果表明,该并发式点到点内存竞争记录算法为每个处理器核添加硬件资源约171B,每千条内存操作指令记录日志大小约2.3B,记录和重演阶段均添加不到1.5%的带宽开销.

基于快速高斯变换的不确定数据聚类算法

数据中不确定性的存在使对其聚类分析时要充分考虑不确定性的影响。针对现有不确定数据聚类算法中构建不确定数据模型以及距离度量时存在的影响结果准确性与聚类性能等问题,提出一种基于快速高斯变换的不确定数据聚类算法。首先在不假设数据分布的前提下,构建符合不确定性分布特征的数据模型;然后结合不确定对象的2个重要特征:属性特征与表示不确定数据分布特征的概率密度函数,度量不确定数据对象间的相似性;并以此为基础提出不确定数据聚类算法;最后在UCI以及真实数据集上的实验结果表明,所提算法在运行效率和聚类准确性方面均能取得较好效果。