Correct, robust and efficient concurrent computation

正确、稳健、高效的并发计算

• 批准号: 41900-2007
• 负责人: Higham, Lisa
• 金额: $ 1.89万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363387
• 关键词: Correct; robust; efficient; concurrent; computation

My research aims for correct, robust and efficient solutions to problems that arise from systems that use many processing components simultaneously.       Asynchronous shared memory architectures use elaborate hardware and software to speed computation.  Message-passing architectures are similarly complicated by a variety of message delivery services, which provide differing constraints on message ordering.  These mechanisms cause subtle, unexpected behaviour that can differ dramatically from what algorithm designers expect.  Thus, without using synchronization primitives, "natural" solutions to "simple" problems are not correct.  The catch is: the elaborate speed-enhancing mechanisms complicate the programming task to such a degree that programmers add excessive synchronization, which, in turn, slows down computation.  Thus, the speed-up advantages intended by special components can be entirely defeated!  A major focus of my research is to construct algorithms that are correct given only the weak guarantees that come with these systems, and that still exploit their speed.       An exciting application of my research is to the new and emerging multi- and many-core computers.  Even commodity desktop and laptop computers these days have "dual cores".  The near horizon promises "many-core" architectures that place possibly hundreds of different processing units on one chip.  Scientists' knowledge of how to program these machines correctly while exploiting their available concurrency is far behind their knowledge of how to build them.  My research aims to define the behaviour of these machines so that they are easier to program.     Even when individual components are very reliable, a failure somewhere in a large system is likely because there are so many components.  A related goal of my research is to design programs that continue to operate well in spite of some dead components, or that can automatically return our systems to correct behaviour after a burst of temporary faults.

我的研究旨在为同时使用许多处理组件的系统所产生的问题提供正确，强大和有效的解决方案。 异步共享存储器体系结构使用复杂的硬件和软件来加速计算。消息传递体系结构同样由于各种消息传递服务而变得复杂，这些服务对消息排序提供了不同的约束。这些机制导致了与算法设计者所期望的截然不同的微妙的、意外的行为。因此，在不使用同步原语的情况下，“简单”问题的“自然”解决方案是不正确的。问题在于：精心设计的加速机制使编程任务复杂化，以至于程序员添加了过多的同步，这反过来又降低了计算速度。因此，特殊组件所期望的加速优势可能完全失败！ 我研究的一个主要重点是构建算法，这些算法在这些系统中只有弱保证的情况下是正确的，并且仍然利用它们的速度。 我的研究的一个令人兴奋的应用是新兴的多核和众核计算机。即使是商用台式机和笔记本电脑这些天有“双核”。近地平线承诺“众核”在一个芯片上放置可能数百个不同处理单元的架构。科学家对如何正确编程这些机器同时利用其可用并发性的知识远远落后于他们对我的研究旨在定义这些机器的行为，以便它们更容易编程。 即使单个组件非常可靠，但由于组件太多，大系统中的某个地方也可能出现故障。我的研究目标之一是设计程序，使其在某些组件失效的情况下仍能继续良好运行，或者使系统在突发临时故障后自动恢复正常行为。