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.     

设计沟通中的噪音——从传播学角度看设计沟通中的困难

文章从传播学的角度探讨设计沟通过程中的困难。设计沟通是贯穿于整个设计管理活动的重要环节,是传达信息的主要途径,但在实践过程中却经常遇到困难,导致设计活动无法顺利进行。文章通过引入噪音的概念,分析设计沟通的困难产生的原因,并利用传播学的理论提出通过冗余调节噪音的想法,以解决设计沟通中的问题。     

浅谈光纤通信新技术的应用与研究

在长途通信网和市话通信网中光纤通信网代替电缆通信网已成为被世界所公认的事实。此时因为通信距离影响,导致利用率的不断下降,所以为光纤通信取得进一步发展,必须寻找新的途径,采用新的技术。本文首先简要概述光纤通信技术特点,然后阐明光纤通信新技术的实践应用,最后进行对光纤通信新技术的研究探讨。     

智能家居系统中的短信收发程序设计

针对智能家居系统中安防报警信息实时收发及家电远程控制的需求,提出使用3G模块收发短信的方法,并设计了实现短信同时收发功能的软件架构。实验结果表明,该方法简单实用,能够满足智能家居系统的要求。     

卫星宽带网络系统的研究与分析

本文主要介绍了卫星宽带网络系统的基本原理、技术特点、发展现状和应用趋势,通过研究和分析,证明了卫星宽带网络在信息通信领域具有广阔的应用前景。     

Randomized function evaluation on a ring

LetR be a unidirectional asynchronous ring ofn identical processors each with a single input bit. Letf be any cyclic nonconstant function ofn boolean variables. Moran and Warmuth (1986) prove that anydeterministic algorithm that evaluatesf onR has communication complexity (n logn) bits. They also construct a family of cyclic nonconstant boolean functions that can be evaluated inO(n logn) bits by a deterministic algorithm.This contrasts with the following new results:

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

新型的数字音频系统—数字盒式磁带（DCC）原理

数字盒式磁带录音机,简称DCC,是一种将现有的盒式磁带与数字声频相结合的产物。它采用了新的有效的精确自适应子带编码技术,简称PASC,使重放的声音达到CD的音质。PASC依据数字声频中两个新的原理:与人耳的听觉特性相适应原理和有效的自适原应理。DCC系统可以与模拟音乐盒带兼容,现有的盒带可以在DCC放音设备上重放。     

基于ADE7755的单相电子式电能表设计

单相电子式电能表以单片机ATmega128作为核心控制芯片,采用高精度电能计量芯片ADE7755采集电量,实现电能计量、电价分时段计算、电量存储和显示、RS485和红外通信等功能。本文介绍了电能表的硬件组成和功能模块的作用,给出了电能计量模块、RS485和红外通信模块的硬件原理图,给出了主程序流程图。经实验测试,该电能表的技术指标符合IEC62053-21标准。     

一种PC式数字录像机软件系统的设计与实现

介绍了一种PC(个人计算机)式数字录像机软件系统的设计与实现,给出了该软件系统的组成框架,对系统主要功能的设计与实现进行了简介,包括图像预览、录像与回放、移动侦测与遮挡、电子地图等。文章给出了系统设计中的多厂家设备支持、系统性能优化两个关键问题的设计与实现。该PC式数字录像机软件系统界面友好、功能完善、运行稳定,用户易于掌握使用,同时具有良好的可扩展性,在实际使用中效果良好。