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

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

• 批准号: 0540600
• 负责人: Darko Stefanovic
• 金额: $ 18万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-04-01 至 2010-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0540600&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.

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