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.     

基于进化计算的兴趣建模

为实现对个体的兴趣建模,提出基于进化计算的建模(Evolutionary Computation Based Modeling,ECBM)方法。该方法采用定性和定量相结合的方式对个体的兴趣系统进行建模,首先通过定性分析构建个体的兴趣模型框架,然后通过进化计算(Evolutionary Computation)方法对模型参数自动进化。实验结果表明,ECBM能够通过数据驱动模式优化模型参数,并利用更新信息进化模型,使其不断逼近真实系统。     

A note on circle packing

The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parallelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit (GPU) on commodity hardware. The speedups so achieved are discussed based on a number of experiments.     

基于中值滤波和梯度锐化的边缘检测

实现一种基于中值滤波和梯度锐化的边缘检测方法。首先采用既能过滤噪声又能保护边缘信息的中值滤波对图像进行平滑处理。然后采用梯度锐化加强边缘像素强度,通过简单的二值化获得图像的初始边缘,系统采用连通区域标记的方法去除位于图像封闭边界内的残留黑块。最后通过实验结果与人工提取的结果比较,进行误差分析,找出本文算法的不足之处,以便对该算法进行改进。实践证明,本文的边缘检测方法对含有噪声点且灰度分布比较均匀的图像有很好的效果。     

基于边缘检测的保特征的图像缩放算法

针对Seam Carving算法在实现图像缩放的过程中,对图像边缘几何特征造成破坏的现象,提出一种基于边缘检测的改进Seam Carving算法。首先在Seam Carving算法计算低能量线的同时引入图像边缘检测,其次确定低能量线与边缘的交点,进而提升交点邻域的能量,分散过于集中的低能量线。仿真实验结果表明,该算法能够有效减少Seam Carving算法缩放图像后产生的畸变,很好地保持了图像的重要几何特征。     

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

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

移动边缘计算中基于中继辅助计算方法综述*

为了满足下一代网络在覆盖范围、部署成本以及容量方面的挑战,移动边缘计算（MEC）通常需要借助中继节点的辅助来完成计算密集型和延迟敏感型的任务。首先介绍了基于中继辅助MEC系统的基本架构,之后从任务卸载、资源分配和中继节点选择三方面对基于中继辅助MEC系统最新的研究方法进行归纳总结。更进一步,针对现有方法可能存在的问题与挑战进行了讨论与分析,并提出一些可行的解决方案为后续研究发展提供参考。     

基于负载预测的微服务混合自动扩展

由于边缘云没有比中心云更强大的计算处理能力,在应对动态负载时很容易导致无意义的扩展抖动或资源处理能力不足的问题,所以在一个真实的边缘云环境中对微服务应用程序使用两个合成和两个实际工作负载进行实验评估,并提出了一种基于负载预测的混合自动扩展方法（predictively horizontal and vertical pod autoscaling,Pre-HVPA）。该方法首先采用机器学习对负载数据特征进行预测,并获得最终负载预测结果。然后利用预测负载进行水平和垂直的混合自动扩展。仿真结果表明,基于该方法所进行自动扩展可以减少扩展抖动和容器使用数量,所以适用于边缘云环境中的微服务应用。     

Secure authentication scheme for passive C1G2 RFID tags

Privacy and security concerns inhibit the fast adaption of RFID technology for many applications. A number of authentication protocols that address these concerns have been proposed but real-world solutions that are secure, maintain low communication cost and can be integrated into the ubiquitous EPCglobal Class 1 Generation 2 tag protocol (C1G2) are still needed and being investigated. We present a novel authentication protocol, which offers a high level of security through the combination of a random key scheme with a strong cryptography. The protocol is applicable to resource, power and computationally constraint platforms such as RFID tags. Our investigation shows that it can provide mutual authentication, untraceability, forward and backward security as well as resistance to replay, denial-ofth-service and man-in-the-middle attacks, while retaining a competitive communication cost. The protocol has been integrated into the EPCglobal C1G2 tag protocol, which assures low implementation cost. We also present a successful implementation of our protocol on real-world components such as the INTEL WISP UHF RFID tag and a C1G2 compliant reader.