Locality-preserving hash functions for general purpose parallel computation

Consider the problem of efficiently simulating the shared-memory parallel random access machine (PRAM) model on massively parallel architectures with physically distributed memory. To prevent network congestion and memory bank contention, it may be advantageous to hash the shared memory address space. The decision on whether or not to use hashing depends on (1) the communication latency in the network and (2) the locality of memory accesses in the algorithm.We relate this decision directly to algorithmic issues by studying the complexity of hashing in the Block PRAM model of Aggarwal, Chandra, and Snir, a shared-memory model of parallel computation which accounts for communication locality. For this model, we exhibit a universal family of hash functions having optimal locality. The complexity of applying these hash functions to the shared address space of the Block PRAM (i.e., by permuting data elements) is asymptotically equivalent to the complexity of performing a square matrix transpose, and this result is best possible for all pairwise independent universal hash families. These complexity bounds provide theoretical evidence that hashing and randomized routing need not destroy communication locality, addressing an open question of Valiant.This work was started when the author was a student at Oxford University, supported by a National Science Foundation Graduate Fellowship and a Rhodes Scholarship. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation or the Rhodes Trust.     

DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

多用户动态节能资源竞争计算卸载策略

针对移动边缘计算环境下,移动设备的计算、续航、存储能力的不足,导致其响应延迟、电池寿命降低等问题,设计了一种动态节能资源竞争计算卸载（DERCO）策略。该策略综合考虑了信道容量以及设备间的相互干扰等情况,以一种贪婪算法的思想,让所有边缘设备通过迭代竞争信道资源,节能效果最好的设备将获得卸载机会,再利用一次性卸载方法,根据实时的信道状况和卸载速率进行动态的细粒度子任务卸载决策。实验结果表明,该策略优于一种近似协同计算卸载方案,有效降低了设备的能耗与时延。     

大规模认知无线电网络的时延分析

时延作为无线网络的最基本的性能之一,对网络信息分发、路由协议设计、节点部署等都具有重要意义。与传统的无线网络不同,认知无线电网络的频谱资源具有动态变化性,该特性会对网络时延产生极大的影响。因此,如何对动态频谱环境下的大规模认知无线电网络进行时延分析,是一项很具挑战性的课题。为此,首先对动态频谱环境进行建模,将认知用户的频谱接入过程建模为一个连续时间的马尔可夫链,并建立认知用户的生存函数来量化授权用户活动以及信道数量对频谱环境的影响;其次,将上述模型与首次通过渗流理论结合起来,研究了大规模认知无线电网络时延的伸缩规律,并获取了更为精确的时延与距离比的上限值。理论分析及仿真结果表明,动态频谱环境与密度一样会对时延产生极大影响。研究结论对认知无线电网络的设计具有重要的指导意义。     

无线传感器网络中的改进数据聚集调度算法

针对现有聚集数据调度近似算法具有较高延时上界的问题,提出一种改进的聚集数据调度近似算法。建立一棵根在中心结点的广度优先搜索树,分层构造一个最大独立集(MIS),使MIS中相邻的2个结点相距两跳。将MIS中的结点连接起来,形成一棵根在中心结点的数据聚集调度树,使结点按数据聚集调度树进行分层数据调度。在数据聚集调度树的构造过程中,对于任意支配点,以最小的结点连接其相距两跳的支配点。对于2个相邻支配点的公共邻居支配点,通过在距中心点最近的支配点加入数据聚集树,使其在数据调度过程中将数据发送给距中心点最近的支配点,从而降低数据的聚集延时。实验结果表明,与SAS算法、Guo’s算法和IAS算法相比,该算法的数据聚集延时更低,其延时上界为14R+△?10。     

基于通信流量特征的隐秘P2P僵尸网络检测

针对目前基于网络的P2P僵尸网络检测中特征建模不完善、不深入的问题, 以及僵尸网络中通信具有隐蔽性的特点, 提出一种对通信流量特征进行聚类分析的检测方法。分析P2P僵尸网络在潜伏阶段的通信流量统计特征, 使用结合主成分分析法和X-means聚类算法的两阶段聚类方法对特征数据集进行聚类分析, 进而达到检测P2P僵尸网络的目的。实验结果表明, 该方法具有较高的检测率和较好的识别准确性, 并保证了较快的执行效率。     

车载安全应用广播性能分析*

在仿真软件NS-2.29和VanetMobiSim1.1下,搭建了车载通信网络仿真平台,讨论了广播信标信息在不同距离下的接收率,并对两类广播信息在EDCA方式下的接收率和接入时延进行了深入的分析和比较。仿真结果表明,隐藏终端导致广播数据的严重丢包而且不同竞争窗口对接入时延有很大的影响,尤其是在信道负荷比较重时。最后指出了可行的解决思路。     

基于可变步长的访存延迟测量模型的研究与实现

评测访存延迟对于优化应用访存模式和数据放置有重要的指导意义,然而数据Cache、多线程、数据预取等技术却严重干扰了访存延迟测量的精度。设计并实现了基于可变步长的访存延迟测量模型,在一块空间内根据用户指定的步长创建访问序列环,循环访问这个序列得出平均时间,即为访存延迟。最后对Intel的通用处理器和飞腾处理器在不同数据大小、步长、线程数等情况下的访存延迟进行了测量比较,该模型能够显示存储层次并精确显示测量延迟。     

M5-EDGE分布式取指模型设计

为解决M5-edge模拟器的理想化集总式取指令结构对基于EDGE体系结构设计空间探索的限制问题,对原模拟器的取指令前段进行分布式设计,包括总体的功能、具体的取指单元及单元间的互连网络设计,并在取指令块头的方式上设计了固定方式和循环方式两种方案.通过对实现后的结构进行在不同分布单元数量条件下的仿真分析,得到从理想集总式取指结构到实际分布式结构的性能下降关系和不同取指令块头方式的优劣.通过进一步分析,得出通信延迟和缓存缺失率对处理器性能的影响.     

An underwater acoustic MAC protocol using reverse opportunistic packet appending

Underwater communication primarily utilizes propagation of acoustic waves in water. Its unique characteristics, including slow propagation speed and low data rates, pose many challenges to Media Access Control (MAC) protocol design. In most existing handshaking-based underwater MAC protocols, only an initiating sender can transmit data packets to its intended receiver after a channel reservation through a Request-to-Send (RTS)/Clear-to-Send (CTS) handshake. This conventional single-node transmission approach is particularly inefficient in underwater environments, as it does not account for long propagation delays. To improve channel utilization in high latency environments, we propose a novel approach that exploits the idle waiting time during a 2-way handshake to set up concurrent transmissions from multiple nodes. The sender can coordinate multiple first-hop neighbors (appenders) to use the current handshake opportunity to transmit (append) their data packets with partially overlapping transmission times. After the sender finishes transmitting its packets to its own receiver, it starts to receive incoming appended packets that arrive in a collision-free packet train. This not only reduces the amount of time spent on control signaling, but it also greatly improves packet exchange efficiency. Based on this idea, we propose an asynchronous, single-channel handshaking-based MAC protocol based on reverse opportunistic packet appending (ROPA). From extensive simulations (single- and multi-hop networks) and comparisons with several existing MAC protocols, including MACA-U, MACA-UPT, BiC-MAC, Slotted-FAMA, DACAP, unslotted Aloha, we show that ROPA significantly increases channel utilization and offers performance gains in throughput and delay while attaining a stable saturation throughput.