共查询到20条相似文献,搜索用时 125 毫秒
1.
This paper presents a fundamentally new approach to global register allocation that optimally allocates registers and optimally places spill code, significantly decreasing spill code overhead compared with the traditional graph-coloring approach. The Optimal Register Allocation (ORA) approach formulates global register allocation as a 0–1 integer programming problem, incorporating all aspects of register allocation within a unified framework, including copy elimination, live range splitting, rematerialization, callee and caller register spilling, special instruction-operand requirements, and paired registers. A prototype ORA allocator is built into the Gnu C Compiler (GCC). For the SPEC92 integer benchmarks, the ORA allocator actually produces a net decrease of more than 100 million cycles across the entire benchmark set, because the dynamic copies the ORA allocator removes exceed the dynamic loads and stores that are inserted. In contrast, the GCC allocator and a Chaitin-style graph-coloring allocator each cause a net increase of more than 1 billion cycles. Because global register allocation is NP-complete, optimal register allocation has been considered intractable. However, the run-time complexity of the ORA approach is shown experimentally to be O(n3). A profile-guided hybrid allocation approach is proposed that uses the ORA allocator for the performance critical regions in the performance critical functions, while using a graph-coloring allocator for the non-critical functions and regions. An ORA-GCC hybrid allocator takes an average of 4.6 seconds per function to produce an allocation that is within 1% of optimal for 97% of the SPEC92 integer benchmark functions, showing that the hybrid allocator is practical as an advanced optimization for performance-critical codes. 相似文献
2.
经典的粒子群是一个有效的寻找连续函数极值的方法,结合遗传算法的思想提出的混合粒子群算法来解决0-1整数规划问题,经过比较测试,6种混合粒子群算法的效果都比较好,特别交叉策略A和变异策略C的混合粒子群算法是最好的且简单有效的算法.对于目前还没有好的解法的组合优化问题,很容易地修改此算法就可解决. 相似文献
3.
一类非线性整数规划问题的计算机求解 总被引:2,自引:0,他引:2
文章针对一类具有特殊性质的非线性整数规划问题,提出了一种具有剔除选择的计算机求解的方法。该求解方法的提出,对解决现实生活中这一类非线性整数规划问题,提供了一种切实可行的途径,这为此类问题的决策提供了有效的手段。 相似文献
4.
In this paper, we propose a branch-and-partition algorithm to solve the integer linear programming problem with multi-criteria and multi-constraint levels (MC-ILP). The procedure begins with the relaxation problem that is formed by ignoring the integer restrictions. In this branch-and-partition procedure, an MC linear programming problem is adopted by adding a restriction according to a basic decision variable that is not integer. Then the MC-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the constraint parameter for a regular MC linear programming problem. We use parameter partition to divide the (λ, γ) space for integer solutions of MC problem. The branch-and-partition procedure terminates when every potential basis for the relaxation problem is a potential basis for the MC-ILP problem. A numerical example is used to demonstrate the proposed algorithm in solving the MC-ILP problems. The comparison study and discussion on the applicability of the proposed method are also provided. 相似文献
5.
6.
7.
8.
《软件》2018,(2):188-190
"拍照赚钱"是移动互联网下的一种自助式服务模式。用户下载APP,注册成为APP的会员,然后从APP上领取需要拍照的任务(比如上超市去检查某种商品的上架情况),赚取APP对任务所标定的酬金。这是一种基于移动互联网的自助式劳务众包平台,APP即为该平台运行的核心,而实际情况下,多个任务可能因为位置比较集中,导致用户会争相选择,一种考虑是将这些任务联合在一起打包发布,在这种考虑下,就需要修改原本的定价模型来匹配这种打包方案。针对这个问题,我们使用0-1规划、聚类分析等数学方法,运用了Lingo和XGeocoding软件,并结合实际情况,确定了定价模型。 相似文献
9.
建立物流配送中心选址问题的0-1混合整数规划模型,并结合目标排序法和改进的PSRS设计求解0-1规为1的并行算法。改进PSRS可将各个目标的验证任务进行均衡划分,并提交给各个处理器并行进行可行性验证,算法理论上具有接近处理器个数P的加速比。 相似文献
10.
0-1背包问题是经典的NP问题.本文对0-1背包问题的动态规划算法进行了分析,用Visual C 实现该算法. 相似文献
11.
12.
DNA折纸是一种全新的DNA自组装方法。将一个由DNA折纸卡槽、双态DNA机器、DNA行走机器人组装而成的动态折纸应用于求解0-1规划问题。其中DNA折纸卡槽由1条M13脚手架链和202条钉书钉链折叠而成。双态DNA机器分为不修饰和修饰金纳米颗粒两种情况,对应于0-1规划问题约束变量的取值为0或者1。DNA折纸卡槽和DNA双态机器组装成折纸基底。DNA行走机器人是7条单链折叠成的带有粘性末端的DNA折纸。在链的驱动下,DNA行走机器人在折纸基底上顺时针旋转行走,每步旋转120°。DNA行走机器人每走两步,与折纸基底上的DNA双态机器进行链置换,接收修饰的金纳米颗粒。当整个动态行走过程结束,根据透射电镜下DNA行走机器人接收的金纳米颗粒的大小和个数来判断约束变量的取值是否为可行解。该计算模型采用模块化结构,DNA折纸卡槽、双态DNA机器、DNA行走机器人等折纸均单独设计,且采用透射电镜读解,因而提高了模型实现的可行性。 相似文献
13.
0-1规划是决策变量仅取值0或1的一类特殊的整数规划,具有深刻的背景和广泛的应用。植物的生长取决于对光资源的获取,本文将植物生长的竞争机制引入蚁群算法,给出了一种求解0-1规划的生长竞争蚁群优化算法。算法定义了0-1规划的生长竞争演化规则,建立了算法模型,提高了蚁群的全局优化能力。通过对多个实例的求解和验证,结果表明该方法是一种有效的方法。 相似文献
14.
15.
The PID relay auto-tuner of Astrom–Hagglund is one of the simplest and most robust auto-tuning techniques for process controllers and has been successfully applied to industry for more than 15 years. This tuner is based on an approximate estimation of the critical point on the process frequency response from relay oscillations. Many developments have recently been reported to extend its applications. It turns out that more and accurate information on process dynamics can be obtained from the same relay test with the help of new identification techniques, and used to tune PID controllers better. Extensions are also made to tune model-based advanced controllers and multivariable controllers. The present paper reviews these developments and shows the state-of art in relay auto-tuning of process controllers. 相似文献
16.
17.
18.
Since many domains are constantly evolving, the associated domain specific languages (DSL) inevitably have to evolve too, to retain their value. But the evolution of a DSL can be very expensive, since existing words of the language (i.e. programs) and tools have to be adapted according to the changes of the DSL itself. In such cases, these costs seriously limit the adoption of DSLs.This paper presents Lever, a tool for the evolutionary development of DSLs. Lever aims at making evolutionary changes to a DSL much cheaper by automating the adaptation of the DSL parser as well as existing words and providing additional support for the correct adaptation of existing tools (e.g. program generators). This way, Lever simplifies DSL maintenance and paves the ground for bottom-up DSL development. 相似文献
19.
整数规划是NP困难的经典问题之一,将传统的二分搜索方法推广应用到整数规划的解空间中,提出一种求解整数规划的新算法。当问题变量数固定时,算法的时间复杂性为0(Llog^L),其中L为问题实例的输入规模,理论分析和实验结果表明:新算法不仅初步解决了目前求解系数呈指数增长的整数规划问题时存在的实质性困难,可直接用于此类大规模问题的求解,同时由于其特剐适合并行处理的算法结构,可望为一般大规模整数规划问题的精确求解提供新的途径。 相似文献
20.
《IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans : a publication of the IEEE Systems, Man, and Cybernetics Society》2009,39(2):460-465