ST-CRTS: Collaborative Research: Algorithmic Optimizations in Dynamic Programming Environments

ST-CRTS：协作研究：动态编程环境中的算法优化

• 批准号: 0540997
• 负责人: Amer Diwan
• 金额: $ 20万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-04-01 至 2011-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0540997&HistoricalAwards=false
• 关键词: ST; CRTS; Collaborative; Research; Algorithmic

BackgroundRapid increases in computer performance, according to Moores law, have enabled software architects todesign software of ever increasing functionality and complexity. Consequently, consumers expect softwarethat grows in functionality and can process larger data sets with every new release (e.g., huge spreadsheetsor streaming high-quality video). Unfortunately, since Moores law will likely not hold in the near future,owing to physical limitations such as wire delays and heat dissipation, hardware speedups will not keeppace with the demands of software. Thus, to meet the performance requirements of new software, one mustlook to software techniques. The proposed work will explore a new approach, algorithmic optimizations invirtual machines, to provide the performance for next generations of software.Intellectual Merit-A system for marking implementations of algorithms, data structures, and their uses. A VM thatknows about this system can exploit the information for connecting uses with suitable implementations.A VM that does not know about this system still executes the code correctly but without itsperformance benefits.-An implementation within a Java virtual machine that exploits the information for improving performance.This implementation support includes modifications to the garbage collector (for migratingdata from one representation to another), compiler (for inlining away the calls), and scheduler (forscheduling profile collection threads with lower priority).-A collection of libraries and applications marked to exploit algorithmic optimizations. This will formpart of the evaluation for the proposed work.Broader ImpactThe infrastructure developed as part of this research will be used in undergraduatealgorithms classes to give students deep knowledge about the strengths and limitations of commonly used algorithms and data structures. This research will provides the performance necessary for meeting the needs of future software systems.

背景根据摩尔定律，计算机性能的快速增长使软件架构师能够设计出功能和复杂性不断增加的软件。因此，消费者希望软件在功能上有所增长，并且可以在每个新版本中处理更大的数据集(例如，巨大的电子表格或流媒体高质量视频)。不幸的是，由于摩尔定律可能不会在不久的将来成立，由于线路延迟和散热等物理限制，硬件加速将跟不上软件的需求。因此，要满足新软件的性能要求，就必须关注软件技术。这项拟议的工作将探索一种新的方法，即虚拟机中的算法优化，以提供下一代软件的性能。智能优点-用于标记算法、数据结构及其用途的实现的系统。了解该系统的VM可以利用该信息来将使用与适当的实现连接起来。不了解该系统的VM仍然正确地执行代码，但没有其性能优势。-Java虚拟机中利用该信息来提高性能的实现。该实现支持包括对垃圾收集器(用于将数据从一种表示迁移到另一种表示)、编译器(用于内联调用)和调度器(用于调度优先级较低的配置文件收集线程)的修改。-标记为利用算法优化的库和应用程序的集合。这将是对拟议工作的评估的一部分。广泛影响作为本研究的一部分开发的基础设施将用于本科生的算法课程，让学生深入了解常用算法和数据结构的优点和局限性。这项研究将提供满足未来软件系统需求所需的性能。