首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
CS 551代写、c/c++设计编程代做
项目预算:
开发周期:
发布时间:
要求地区:
CS 551 Systems Programming, Fall 2024
Programming Project 2
In this project we are going to simulate the MapReduce framework on a single machine using
multi-process programming.
1 Introduction
In 2004, Google (the paper “MapReduce: Simplified Data Processing on Large Clusters” by J.
Dean and S. Ghemawat) introduced a general programming model for processing and generating
large data sets on a cluster of computers.
The general idea of the MapReduce model is to partition large data sets into multiple splits,
each of which is small enough to be processed on a single machine, called a worker. The data
splits will be processed in two phases: the map phase and the reduce phase. In the map phase, a
worker runs user-defined map functions to parse the input data (i.e., a split of data) into multiple
intermediate key/value pairs, which are saved into intermediate files. In the reduce phase, a
(reduce) worker runs reduce functions that are also provided by the user to merge the intermediate
files, and outputs the result to result file(s).
We now use a small data set (the first few lines of a famous poem by Robert Frost, see Figure
1) to explain to what MapReduce does.
Figure 1: A small data set to be processed by MapReduce.
To run MapReduce, we first split the dataset into small pieces. For this example, we will split
the dataset by the four lines of the poem (Figure 2).
Figure 2: Partitioning the input data set into multiple splits.
The MapReduce framework will have four workers (in our project, the four workers are four
processes that are forked by the main program. In reality, they will be four independent machines)
to work on the four splits (each worker is working on a split). These four map worker will each
run a user-defined map function to process the split. The map function will map the input into
a series of (key, value) pairs. For this example, let the map function simply count the number of
each letter (A-Z) in the data set.
Figure 3: The outputs of the map phase, which are also the inputs to the reduce phase.
The map outputs in our example are shown in Figure 3. They are also the inputs for the
reduce phase. In the reduce phase, a reduce worker runs a user-defined reduce function to merge
the intermediate results output by the map workers, and generates the final results (Figure 4).
Figure 4: The final result
2 Simulating the MapReduce with multi-process programming
2.1 The base code
Download the base code from the Brightspace. You will need to add your implementation into
this base code. The base code also contains three input data sets as examples.
2.2 The working scenario
In this project, we will use the MapReduce model to process large text files. The input will be a
file that contains many lines of text. The base code folder contains three example input data files.
We will be testing using the example input data files, or data files in similar format.
A driver program is used to accept user inputs and drive the MapReduce processing. The
main part of driver program is already implemented in main.c. You will need to complete the
mapreduce() function, which is defined in mapreduce.c and is called by the driver program.
A Makefile has already been given. Running the Makefile can give you the executable of the driver
program, which is named as “run-mapreduce”. The driver program is used in the following way:
./run-mapreduce "counter"|"finder" file_path split_num [word_to_find]
where the arguments are explained as follows.
• The first argument specifies the type of the task, it can be either the “Letter counter” or
the “Word conter” (explained later).
• The second argument “file path” is the path to the input data file.
• The third argument “split num” specifies how many splits the input data file should be
partitioned into for the map phase.
• The fourth argument is used only for the “Word finder” task. This argument specifies the
word that the user is trying to find in the input file.
The mapreduce() function will first partition the input file into N roughly equal-sized splits,
where N is determined by the split num argument of the driver program. Note that the sizes of
each splits do not need to be exactly the same, otherwise a word may be divided into two different
splits.
Then the mapreduce() forks one worker process per data split, and the worker process will
run the user-defined map function on the data split. After all the splits have been processed, the
first worker process forked will also need to run the user-defined reduce function to process all the
intermediate files output by the map phase. Figure 5 below gives an example about this process.
split 0
split 1
split 2
Driver
Program
map
worker 0
reduce
worker
map
worker 2
map
worker 3
“mr-0.itm”
“mr-1.itm”
“mr-2.itm”
“mr-3.itm”
map
worker 1
(1) partition
(2) fork
(3) userdefined
map
(5) userdefined
reduce
“mr.rst”
Input
data file
Intermediate
files
Result
file
PID=1001
PID=1002
PID=1003
PID=1004
PID=1001
split 3
Figure 5: An example of the working scenario.
2.3 The two tasks
The two tasks that can be performed by the driver program are described as follows.
The “Letter counter” task is similar to the example we showed in Section 1, which is counting
the number of occurrence of the 26 letters in the input file. The difference is the intermediate file
and the final result file should be written in the following format:
A number-of-occurrences
B number-of-occurrences
...
Y number-of-occurrences
Z number-of-occurrences
The “Word finder” task is to find the word provided by user (specified by the “word to find”
argument of the driver program) in the input file, and outputs to the result file all the lines that
contain the target word in the same order as they appear in the input file. For this task, you
should implement the word finder as a whole word match, meaning that the function should only
recognize complete words that match exactly(case-sensitive) with the specified search terms. And
if multiple specified words are found in the same line, you only need to output that line once.
2.4 Other requirements
• Besides the mapreduce() function defined in mapreduce.c, you will also need to complete the map/reduce functions of the two tasks (in usr functions.c.)
• About the interfaces listed in “user functions.h” and “mapreduce.h”:
– Do not change any function interfaces.
– Do not change or delete any fields in the structure interfaces (but you may add additional fields in the structure interface if necessary).
The above requirements allow the TA to test your implementations of worker logic and user
map/reduce functions separately. Note that violation to these requirements will result in 0
point for this project.
• Use fork() to spawn processes.
• Be careful to avoid fork bomb (check on Wikipedia if you are not familiar with it). A fork
bomb will result in 0 point for this project.
• The fd in the DATA SPLIT structure should be a file descriptor to the original input data
file.
• The intermediate file output by the first map worker process should be named as “mr-0.itm”,
the intermediate file by the second map worker process should be named as “mr-1.itm”, ...
The result file is named as “mr.rst” (already done in main.c).
• Program should not automatically delete the intermediate files once they are created. They
will be checked when grading. But your submission should not contain any intermediate
files as they should be created dynamically.
3 Submit your work
Compress the files: compress your README file, all the files in the base code folder, and
any additional files you add into a ZIP file. Name the ZIP file based on your BU email ID. For
example, if your BU email is “abc@binghamton.edu”, then the zip file should be “proj2 abc.zip”.
Submission: submit the ZIP file to Brightspace before the deadline.
3.1 Grading guidelines
(1) Prepare the ZIP file on a Linux machine. If your zip file cannot be uncompressed, 5 points
off.
(2) If the submitted ZIP file/source code files included in the ZIP file are not named as specified
above (so that it causes problems for TA’s automated grading scripts), 10 points off.
(3) If the submitted code does not compile:
1 TA will try to fix the problem (for no more than 3 minutes);
2 if (problem solved)
3 1%-10% points off (based on how complex the fix is, TA’s discretion);
4 else
5 TA may contact the student by email or schedule a demo to fix the problem;
6 if (problem solved)
7 11%-20% points off (based on how complex the fix is, TA’s discretion);
8 else
9 All points off;
So in the case that TA contacts you to fix a problem, please respond to TA’s email promptly
or show up at the demo appointment on time; otherwise the line 9 above will be effective.
(4) If the code is not working as required in this spec, the TA should take points based on the
assigned full points of the task and the actual problem.
(5) Lastly but not the least, stick to the collaboration policy stated in the syllabus: you may
discuss with your fellow students, but code should absolutely be kept private.
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
代写csc1001、代做python设计程...
2024-12-24
代写practice test preparatio...
2024-12-24
代写bre2031 – environmental...
2024-12-24
代写ece5550: applied kalman ...
2024-12-24
代做conmgnt 7049 – measurem...
2024-12-24
代写ece3700j introduction to...
2024-12-24
代做adad9311 designing the e...
2024-12-24
代做comp5618 - applied cyber...
2024-12-24
代做ece5550: applied kalman ...
2024-12-24
代做cp1402 assignment - netw...
2024-12-24
代写comm751/comm752 big data...
2024-12-24
代写business 114 accounting ...
2024-12-24
代做comp 273 project templat...
2024-12-24
热点标签
mktg2509
csci 2600
38170
lng302
csse3010
phas3226
77938
arch1162
engn4536/engn6536
acx5903
comp151101
phl245
cse12
comp9312
stat3016/6016
phas0038
comp2140
6qqmb312
xjco3011
rest0005
ematm0051
5qqmn219
lubs5062m
eee8155
cege0100
eap033
artd1109
mat246
etc3430
ecmm462
mis102
inft6800
ddes9903
comp6521
comp9517
comp3331/9331
comp4337
comp6008
comp9414
bu.231.790.81
man00150m
csb352h
math1041
eengm4100
isys1002
08
6057cem
mktg3504
mthm036
mtrx1701
mth3241
eeee3086
cmp-7038b
cmp-7000a
ints4010
econ2151
infs5710
fins5516
fin3309
fins5510
gsoe9340
math2007
math2036
soee5010
mark3088
infs3605
elec9714
comp2271
ma214
comp2211
infs3604
600426
sit254
acct3091
bbt405
msin0116
com107/com113
mark5826
sit120
comp9021
eco2101
eeen40700
cs253
ece3114
ecmm447
chns3000
math377
itd102
comp9444
comp(2041|9044)
econ0060
econ7230
mgt001371
ecs-323
cs6250
mgdi60012
mdia2012
comm221001
comm5000
ma1008
engl642
econ241
com333
math367
mis201
nbs-7041x
meek16104
econ2003
comm1190
mbas902
comp-1027
dpst1091
comp7315
eppd1033
m06
ee3025
msci231
bb113/bbs1063
fc709
comp3425
comp9417
econ42915
cb9101
math1102e
chme0017
fc307
mkt60104
5522usst
litr1-uc6201.200
ee1102
cosc2803
math39512
omp9727
int2067/int5051
bsb151
mgt253
fc021
babs2202
mis2002s
phya21
18-213
cege0012
mdia1002
math38032
mech5125
07
cisc102
mgx3110
cs240
11175
fin3020s
eco3420
ictten622
comp9727
cpt111
de114102d
mgm320h5s
bafi1019
math21112
efim20036
mn-3503
fins5568
110.807
bcpm000028
info6030
bma0092
bcpm0054
math20212
ce335
cs365
cenv6141
ftec5580
math2010
ec3450
comm1170
ecmt1010
csci-ua.0480-003
econ12-200
ib3960
ectb60h3f
cs247—assignment
tk3163
ics3u
ib3j80
comp20008
comp9334
eppd1063
acct2343
cct109
isys1055/3412
math350-real
math2014
eec180
stat141b
econ2101
msinm014/msing014/msing014b
fit2004
comp643
bu1002
cm2030
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!