99爱在线视频这里只有精品_窝窝午夜看片成人精品_日韩精品久久久毛片一区二区_亚洲一区二区久久

合肥生活安徽新聞合肥交通合肥房產生活服務合肥教育合肥招聘合肥旅游文化藝術合肥美食合肥地圖合肥社保合肥醫院企業服務合肥法律

代寫COMP26020、代做c/c++,Java編程設計

時間:2024-03-15  來源:合肥網hfw.cc  作者:hfw.cc 我要糾錯



COMP26020 - Lab exercise for Part III (Compilers)
Register Allocation using Graph Colouring
Background
Computer programs, regardless of the programming language, often use many more variables
than the number of variables that can fit in all CPU registers. When a program is compiled for
execution on a given processor, the compiler needs to consider what variables will stay in
registers and for how long. If we think that moving data from the memory takes several cycles,
there is a performance benefit if the compiler can minimise such transfers. How to do this? By
doing some ‘clever’ register allocation, for example, by making sure that the most frequently used
variables are placed in registers.
To understand the problem, consider the following piece of code:
1. r1=x
2. r2=y
3. r3=r1*r2
4. r4=z
5. r5=r4+r2
6. r6=w
7. r7=r5+r6
8. r8=r7*r3
9. r9=r8+r1
In this piece of code, the programmer has used 9 variables. However, does this mean that 9
registers are needed? To find the answer, let us define the notion of a live range. For any given
variable, there is a live range that starts from the point where a value is assigned to this variable
and lasts until the last time this particular value is used. Note that if a new value is assigned to
the same variable, a new live range starts. For example, a value for r2 is defined in instruction 2.
The last time it is used is in instruction 5, hence, the live range is between 2 and 5. However, if
instruction 4 was r2=z, the live range would be from 2 to 3 and another live range would start at
instruction 4 and end at instruction 5.
To practice, you may want to find all live ranges of the code above. The answer is given: r1:[1,9],
r2:[2,5], r3:[3,8], r4:[4,5], r5:[5,7], r6:[6,7], r7:[7,8], r8:[8,9], r9:[9,9].
Live ranges are important because they indicate how many values need to be live at any given
instruction. For example, the live ranges above tell us that at instruction 6 four values need to be
live. Clearly, the maximum number of values that need to be live at any instruction indicates how
many registers we need to have so that all values (live ranges) can be placed in registers.
However, most importantly, live ranges can guide register allocation: two live ranges that do not
overlap or interfere can use the same register. For example, with the live ranges above, r2 and r6
can share the same register as the corresponding values are needed (or are ‘live’) at different
parts of the code.
Different algorithms have been developed to find how to allocate different live ranges to registers.
This problem is known as register allocation. It is an NP-complete problem, which means that
most of the different solutions proposed over the years are based on heuristics. For additional
information you can refer to Chapter 13 of the ‘Engineering a Compiler’ recommended textbook:
https://www.sciencedirect.com/science/article/pii/B978012088**8000013X
Among the different approaches, register allocation using graph colouring is a common
approach. In register allocation using graph colouring, live ranges are used to create an
interference graph. In this graph, every live range corresponds to a node. There is an edge
between two nodes if the live ranges overlap. Then, register allocation becomes equivalent to the
problem of graph colouring. This is a well-known graph theory problem where the aim is to colour
all nodes of the graph so that two adjacent nodes do not share the same colour. Typically the
goal is to find the smallest number of colours. Every colour corresponds to a register and the
colour of a node corresponds to the register that should be used for a particular live range. There
are various algorithms to colour a graph. Here, we are going to focus on a simple (heuristic)
algorithm, which is known as top-down colouring. The algorithm works as follows:
1. Assume an ordered list of colours (eg, red, black, blue, etc, here denoted by A, B, C, …)
2. Assume an interference graph, where nodes are numbered: 1, 2, 3, …
3. Rank nodes (that is, live ranges) of the interference graph according to the number of
neighbours in descending order. In case of a tie (that is, nodes with the same number of
neighbours) the node with the lowest id takes priority.
4. Follow the ranking to assign colours from the list of colours. For each node, select the first
colour from the list that is not used by the node’s neighbours.
5. Keep following the ranking and repeating step 4 until all nodes are coloured.
Your task
Use a programming language of your choice to write a program that implements graph colouring
as illustrated by the algorithm above, which:
 reads a file that lists an interference graph (input).
 writes a file that lists colours for every node of the graph (output).
The ordered list of colours is given by the upper-case letters of the alphabet: A, B, C, …, Z. There
is a total of 26 colours (or registers).
Input file specification:
A number of lines equal to the number of nodes of the interference graph. Every line contains the
number of a node (consecutive integers in ascending order, starting with 1) and the numbers of
all nodes with which there is interference (not necessarily in ascending order), separated by a
comma. Example test case:
1,2,3,4
2,4,1
3,1
4,1,2
This means that node 1 interferes with nodes 2, 3, and 4. Node 2 interferes with nodes 1 (we
knew this already) and 4. Node 3 interferes with nodes 1 and 4 interferes with nodes 1 and 2.
You can assume that there are no more than 50 nodes, every node has at least one neighbour
and all interferences are correct. Input files that contain characters other than digits, comma, endof-line or do not adhere to the specification above should be rejected with a simple message.
Output file specification:
For every node (in ascending order), write node number and colour. For the example above:
1A
2B
3B
4C
(other test cases may be posted on BB – you are encouraged to create and post your own too)
Your program should take two command line arguments, which indicate the name of the input file
and the name of the output file. E.g.: % <myprogram> input.txt output.txt
Your program should display a simple message if the input does not meet the specifications
above or the algorithm cannot produce a result with 26 colours or less.
You should be able to complete this task after two weeks of scheduled lab sessions when you
can drop in for any questions. The deadline for submission is Friday 15 March, 6pm. You
should submit through gitlab (and the repository 26020-lab4-s-compilers_<your
username>). Your submission should include all source file(s) and a readme file with instructions
on how to compile and run your code and the tag lab4-submission. You should make sure
that you push to the correct repository in line with UG handbook guidelines, tag the
submission properly and all the files for your code to compile, run and work as intended
are included; failure to do so may result in a mark of 0.
Marking (out of 10) will take place according to the following scheme:
 2 marks for producing the output of the example above correctly.
 3 marks for handling input correctly, code readability and sensible comments.
 5 marks for finding the output of additional test cases correctly.
請加QQ:99515681  郵箱:99515681@qq.com   WX:codehelp 

掃一掃在手機打開當前頁
  • 上一篇:代寫CSCI 4176、SQL程序語言代做
  • 下一篇:CEG5301代做、MATLAB編程語言代寫
  • 無相關信息
    合肥生活資訊

    合肥圖文信息
    急尋熱仿真分析?代做熱仿真服務+熱設計優化
    急尋熱仿真分析?代做熱仿真服務+熱設計優化
    出評 開團工具
    出評 開團工具
    挖掘機濾芯提升發動機性能
    挖掘機濾芯提升發動機性能
    海信羅馬假日洗衣機亮相AWE  復古美學與現代科技完美結合
    海信羅馬假日洗衣機亮相AWE 復古美學與現代
    合肥機場巴士4號線
    合肥機場巴士4號線
    合肥機場巴士3號線
    合肥機場巴士3號線
    合肥機場巴士2號線
    合肥機場巴士2號線
    合肥機場巴士1號線
    合肥機場巴士1號線
  • 短信驗證碼 豆包 幣安下載 AI生圖 目錄網

    關于我們 | 打賞支持 | 廣告服務 | 聯系我們 | 網站地圖 | 免責聲明 | 幫助中心 | 友情鏈接 |

    Copyright © 2025 hfw.cc Inc. All Rights Reserved. 合肥網 版權所有
    ICP備06013414號-3 公安備 42010502001045

    99爱在线视频这里只有精品_窝窝午夜看片成人精品_日韩精品久久久毛片一区二区_亚洲一区二区久久

          国产综合欧美| 激情综合自拍| 亚洲专区一区二区三区| 国产精品美女久久久久久久| 一级成人国产| 欧美三区在线视频| 欧美在线视频导航| 在线日韩av片| 欧美日韩亚洲高清一区二区| 亚洲欧美电影在线观看| 在线观看成人av| 欧美日韩国产精品一卡| 亚洲欧美日韩中文视频| 精品二区久久| 国产精品超碰97尤物18| 久久天天躁狠狠躁夜夜爽蜜月 | 激情久久久久| 欧美精品日韩一本| 欧美伊人久久| 亚洲精品在线视频| 国产一区二区在线观看免费播放| 欧美jizzhd精品欧美巨大免费| 亚洲视频精品在线| 在线播放中文字幕一区| 国产精品视频一区二区三区| 蜜臀久久久99精品久久久久久| 亚洲免费视频网站| 亚洲精品欧美日韩专区| 国产一区二区三区电影在线观看| 欧美国产日韩a欧美在线观看| 午夜在线成人av| 99精品国产高清一区二区| 国内偷自视频区视频综合| 欧美视频在线观看一区二区| 美日韩精品视频免费看| 亚洲欧美中文日韩v在线观看| 亚洲人成网站在线播| 国语自产偷拍精品视频偷| 国产精品99免费看 | 一本久道久久综合婷婷鲸鱼| 国内精品久久久| 国产精品久久久久久久一区探花| 欧美激情1区2区| 另类成人小视频在线| 欧美中日韩免费视频| 亚洲综合首页| 亚洲一区激情| 亚洲一二三四久久| 亚洲香蕉视频| 亚洲午夜高清视频| 一区二区成人精品| 99re这里只有精品6| 亚洲精品裸体| 亚洲激情视频网| 亚洲国产精品第一区二区| 好看的亚洲午夜视频在线| 国产婷婷色一区二区三区在线| 国产精品入口| 国产精品视频最多的网站| 欧美视频日韩| 欧美色图天堂网| 欧美日韩高清在线观看| 欧美日韩视频在线第一区| 欧美区一区二| 国产精品成人午夜| 国产精品乱码一区二三区小蝌蚪| 国产精品久久久久久久久久久久久| 欧美日韩免费一区| 欧美视频精品在线观看| 国产精品久久97| 国产日韩精品一区二区三区| 国产色综合网| 精东粉嫩av免费一区二区三区| 尤物在线观看一区| 亚洲国产欧美一区| 夜夜爽av福利精品导航 | 伊人成人网在线看| 亚洲黄色天堂| 亚洲深夜福利视频| 销魂美女一区二区三区视频在线| 久久精品国产久精国产思思| 久久精品国产久精国产思思| 快射av在线播放一区| 欧美黑人国产人伦爽爽爽| 欧美日韩性视频在线| 国产精品久久久久久久免费软件 | 亚洲精品欧美精品| 亚洲视频电影在线| 久久精品成人| 欧美激情综合亚洲一二区| 欧美午夜免费影院| 国语精品一区| 99国产精品久久久久老师| 亚洲一区二区影院| 老妇喷水一区二区三区| 欧美激情影音先锋| 国产精品人人做人人爽人人添 | 亚洲欧洲在线观看| 亚洲一区二区高清| 开元免费观看欧美电视剧网站| 欧美激情在线狂野欧美精品| 国产精品亚洲综合色区韩国| 激情小说另类小说亚洲欧美| 亚洲最新视频在线| 久久福利资源站| 欧美精品日韩www.p站| 国产精品午夜av在线| 在线看片日韩| 午夜视频一区二区| 欧美激情一区二区三区不卡| 国产欧美视频一区二区| 亚洲欧洲日产国产综合网| 亚洲欧美一级二级三级| 欧美国产日韩一区二区| 国产视频丨精品|在线观看| 亚洲精品字幕| 久久中文久久字幕| 国产精品午夜av在线| 99视频在线观看一区三区| 久久人人爽国产| 国产精品视频1区| 亚洲毛片在线免费观看| 久久久久久久精| 国产精品极品美女粉嫩高清在线| 亚洲高清影视| 久久久久久久999| 国产精品丝袜xxxxxxx| 夜夜嗨一区二区三区| 麻豆乱码国产一区二区三区| 国产精品一区一区| 一区二区国产在线观看| 免费观看成人| 在线观看免费视频综合| 欧美有码在线观看视频| 国产精品久久一区二区三区| 亚洲精选成人| 欧美精品日韩综合在线| 亚洲国产日韩欧美在线动漫| 久久精品免费观看| 国产一级精品aaaaa看| 亚洲在线日韩| 国产精品久久77777| 中文欧美在线视频| 国产精品wwwwww| 亚洲视频在线一区| 欧美性jizz18性欧美| 一区二区三区四区国产| 欧美日韩国产天堂| 99国产一区二区三精品乱码| 欧美精品免费在线| 一本久道久久久| 欧美日韩一区二区三| 亚洲手机在线| 国产精品极品美女粉嫩高清在线 | 影音先锋久久资源网| 久久综合影音| 91久久国产综合久久| 欧美激情1区2区| 在线亚洲精品| 国产农村妇女精品一区二区| 欧美在线视频一区| 国产综合色在线| 久久综合网色—综合色88| 亚洲第一中文字幕| 欧美激情视频网站| 一级日韩一区在线观看| 国产精品视频福利| 久久精品成人一区二区三区蜜臀 | 国产精品国产三级国产专区53| 亚洲综合第一页| 国内精品久久久久久| 欧美xx视频| 一区二区欧美视频| 国产乱码精品一区二区三区五月婷| 欧美在线观看天堂一区二区三区| 狠狠久久亚洲欧美| 欧美另类视频在线| 亚洲欧美成人一区二区三区| 国产日韩欧美视频| 欧美电影免费观看高清完整版| 亚洲午夜av在线| 伊人精品在线| 欧美午夜电影网| 久久色中文字幕| 99视频精品在线| 黑人极品videos精品欧美裸| 欧美成人午夜激情在线| 亚洲一区二区三区高清 | 国产午夜精品久久久| 欧美护士18xxxxhd| 性欧美精品高清| 亚洲激情在线视频| 国产久一道中文一区| 久热精品视频在线观看一区| 亚洲网站在线| 亚洲第一在线| 国产网站欧美日韩免费精品在线观看| 欧美高清视频www夜色资源网| 亚洲欧美日韩综合国产aⅴ| 亚洲成人在线视频网站|