Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate ope...Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate operations between global routing and detailed routing are very effective in crosstalk estimation and reduction, the authors propose to incorporate several intermediate steps that are separated in traditional design flow into an integrated routing resource assignment stage, so that the operations could easily cooperate to fully exert their power on crosstalk reduction. An efficient priority-based heuristic algorithm is developed, which works slice by slice. Crosstalk avoidance, and ,nany other aspects that are critical in routing practice including congestion, vias, layer preference, etc., are taken into account. A track reservation strategy is adopted in the algorithm framework to compensate the undesired effects caused by sequential routing. Experimental results on a series of ISPD98 and industrial benchmarks show that the proposed approach is able to reduce capacitive crosstalk by about 70% on average without compromising completion ratio compared with a previously reported graph based algorithm, demonstrating the advantages of the approach.展开更多
Video accelerator is developed for better user experience in video sharing websites such as YouTube. PPLive video accelerator (PPVA), which has the largest number of users in China, is based on peer-to-peer (P2P) ...Video accelerator is developed for better user experience in video sharing websites such as YouTube. PPLive video accelerator (PPVA), which has the largest number of users in China, is based on peer-to-peer (P2P) system. The number of videos and peers in PPVA is by orders of magnitude many times larger than which in traditional P2P video on demand (VoD) system. As a result, even though the resource is sufficient, due to unfairness assignment, the quality of service can hardly satisfy all users. In this paper, we concentrate on the assignment of the fundamental resources in PPVA: storage and bandwidth. The problem of storage assignment is formulated as a nonlinear program (NLP) regarding the number of request as a random variable. The results show that the influence of the variance of requests is not negligible and proportional approach is appropriate only when the mean is much larger than the variance. The criteria about how to locate videos to appropriate peers are also presented, taking into account constrains such as the utilization of total bandwidth, the probability of bandwidth competition and the fairness between videos. Furthermore, the heuristic algorithms of allocating upload bandwidth in centralized and distributed fashion are proposed and evaluated against a widely used strategy (equal allocation) with respect to the balance among videos. Simulation results demonstrate that both algorithms can lead to significant performance improvement.展开更多
With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very impo...With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very important,therefore,many researchers focus on the airport gate and taxiway assignment problem.However,the joint assignment algorithm of airport gates and taxiways with realistic airport data has not been well studied.A greedy algorithm based on joint assignment of airport gates and taxiways using the data of a large hub airport in China is proposed.The objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions.Simulation results show that it outperforms other assignment schemes.展开更多
基金This work is supported by the National Hi-Tech Research & Development 863 Program of China under Grant No. 2004AA1Z14600 and the National Natural Science Foundation of China (NSFC) under Grant No, 60476014.
文摘Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate operations between global routing and detailed routing are very effective in crosstalk estimation and reduction, the authors propose to incorporate several intermediate steps that are separated in traditional design flow into an integrated routing resource assignment stage, so that the operations could easily cooperate to fully exert their power on crosstalk reduction. An efficient priority-based heuristic algorithm is developed, which works slice by slice. Crosstalk avoidance, and ,nany other aspects that are critical in routing practice including congestion, vias, layer preference, etc., are taken into account. A track reservation strategy is adopted in the algorithm framework to compensate the undesired effects caused by sequential routing. Experimental results on a series of ISPD98 and industrial benchmarks show that the proposed approach is able to reduce capacitive crosstalk by about 70% on average without compromising completion ratio compared with a previously reported graph based algorithm, demonstrating the advantages of the approach.
基金supported by the National Basic Research Program of China (2007CB307101)the National Natural Science Foundation of China (60672069,60772043)
文摘Video accelerator is developed for better user experience in video sharing websites such as YouTube. PPLive video accelerator (PPVA), which has the largest number of users in China, is based on peer-to-peer (P2P) system. The number of videos and peers in PPVA is by orders of magnitude many times larger than which in traditional P2P video on demand (VoD) system. As a result, even though the resource is sufficient, due to unfairness assignment, the quality of service can hardly satisfy all users. In this paper, we concentrate on the assignment of the fundamental resources in PPVA: storage and bandwidth. The problem of storage assignment is formulated as a nonlinear program (NLP) regarding the number of request as a random variable. The results show that the influence of the variance of requests is not negligible and proportional approach is appropriate only when the mean is much larger than the variance. The criteria about how to locate videos to appropriate peers are also presented, taking into account constrains such as the utilization of total bandwidth, the probability of bandwidth competition and the fairness between videos. Furthermore, the heuristic algorithms of allocating upload bandwidth in centralized and distributed fashion are proposed and evaluated against a widely used strategy (equal allocation) with respect to the balance among videos. Simulation results demonstrate that both algorithms can lead to significant performance improvement.
基金the National Natural Science Foundation of China(No.U1633115,61571021)the Science and Technology Foundation of Beijing Municipal Commission of Education(No.KM201810005027).
文摘With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very important,therefore,many researchers focus on the airport gate and taxiway assignment problem.However,the joint assignment algorithm of airport gates and taxiways with realistic airport data has not been well studied.A greedy algorithm based on joint assignment of airport gates and taxiways using the data of a large hub airport in China is proposed.The objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions.Simulation results show that it outperforms other assignment schemes.