Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
Use the following commands to make a fresh clone of your repository:
```
git clone -b m7 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git m7
```
## Useful links
* [A guide to the Scala parallel collections](https://docs.scala-lang.org/overviews/parallel-collections/overview.html)
* [The API documentation of the Scala parallel collections](https://www.javadoc.io/doc/org.scala-lang.modules/scala-parallel-collections_2.13/latest/scala/collection/index.html)
* [The API documentation of the Scala standard library](https://www.scala-lang.org/files/archive/api/2.13.4)
* [The API documentation of the Java standard library](https://docs.oracle.com/en/java/javase/15/docs/api/index.html)
**If you have issues with the IDE, try [reimporting the
build](https://gitlab.epfl.ch/lamp/cs206/-/blob/master/labs/example-lab.md#ide-features-like-type-on-hover-or-go-to-definition-do-not-work),
if you still have problems, use `compile` in sbt instead.**
## Exercise
In this exercise, you will implement an array Combiner using internally a doubly linked list of arrays. Your goal is to complete the implementation of the (simplified) Combiner interface, by implementing the `result` method to compute the result array from this array combiner.
Here you can see the declaration of the `DLLCombiner` class and the related `Node` class definition. Look at the `Lib` trait in the `lib.scala` file to find all definitions of relevant functions and classes.
```scala
class Node(val size: Int) {
var value: Array[Int] = new Array(size)
var next: Node = null
var previous: Node = null
var cnt = 0
def add(v: Int) = {
value(cnt) = v
cnt += 1
}
}
// Simplified Combiner interface
// Implements methods += and combine
// Abstract methods should be implemented in subclasses
abstract class DLLCombiner(val chunk_size: Int)
```
`DLLCombiner` class contains the implementation of methods `+=` and `combine`. You should look at them to better understand the structure of this array Combiner, before moving on to solving this exercise.
Your task in the exercise will be to implement the `result` method of the `DLLCombinerImplementation` class. This method should compute the result array from this array combiner. This method should work in parallel according to the Combiner contract. Implement this method efficiently using 4 parallel tasks, by copying the doubly linked list to the array from both ends at the same time. Two threads should start from the start of the list and two from the end. In each case, one thread would be responsible for odd list indexes and the other for even ones.
```scala
class DLLCombinerImplementation(chunk_size: Int = 3) extends DLLCombiner(chunk_size) {
// Computes every other Integer element of data array, starting from the second, up to the middle
def task1(data: Array[Int]) = task {
???
}
// Computes every other Integer element of data array, starting from the first (index 0), up to the middle
def task2(data: Array[Int]) = task {
???
}
// Computes every other Integer element of data array, starting from the last, up to the middle
def task3(data: Array[Int]) = task {
???
}
// Computes every other Integer element of data array, starting from the second to last, up to the middle
// This is executed on the current thread.
def task4(data: Array[Int]) = {
???
}
def result(): Array[Int] = {
val data = new Array[Int](cnt)
???
data
}
}
```
Following the description above, your task in the exercise is to:
- Implement the four tasks to copy parts of the array. Each task is responsible for computing one quarter of the array, as indicated in comments:
+ Task 1: Computes every other Integer element of data array, starting from the second, up to the middle
+ Task 2: Computes every other Integer element of data array, starting from the first (index 0), up to the middle
+ Task 3: Computes every other Integer element of data array, starting from the last, up to the middle
+ Task 4: Computes every other Integer element of data array, starting from the second to last, up to the middle
- Implement the method `result` to compute the result array in parallel using those four tasks.
Hints:
- Note that this doubly linked list implementation uses `null` pointers to represent the absence of nodes. Be careful when working with `null` pointers in your solution, to avoid causing a `NullPointerException`.
- `DLLCombinerImplementation` comes with a private `copyForward` method that you can use in your solution:
```scala
private def copyForward(data: Array[Int], curr: Node, from: Int, to: Int, limit: Int)
```
This method copies certain elements from a doubly linked list to an array, in a way that might be useful for this exercise.
## Examples
Here is one example of the `result` method with intermediate results:
```scala
val combiner1 = DLLCombinerImplementation(4)
combiner1 += 7 // (7)
combiner1 += 2 // (7, 2)
combiner1 += 4 // (7, 2, 4)
combiner1 += 3 // (7, 2, 4, 3)
combiner1 += 9 // (7, 2, 4, 3) <-> (9)
combiner1 += 5 // (7, 2, 4, 3) <-> (9, 5)
combiner1 += 1 // (7, 2, 4, 3) <-> (9, 5, 1)
val res1 = combiner1.result() // (7, 2, 4, 3, 9, 5, 1)
```
In this example, `task1` was responsible for computing elements at index 1, `task2` for computing elements at indexes 0 and 2, `task3` for computing elements at indexes 6 and 4, and `task4` for computing elements at indexes 5 and 3.
Here is another example with combining:
```scala
val c1 = DLLCombinerImplementation(4)
c1 += 7 // (7)
c1 += 2 // (7, 2)
c1 += 4 // (7, 2, 4)
c1 += 3 // (7, 2, 4, 3)
c1 += 9 // (7, 2, 4, 3) <-> (9)
c1 += 5 // (7, 2, 4, 3) <-> (9, 5)
c1 += 1 // (7, 2, 4, 3) <-> (9, 5, 1)
val c2 = DLLCombinerImplementation(4)
c2 += 6 // (6)
c2 += 8 // (6, 8)
c2 += 5 // (6, 8, 5)
c2 += 1 // (6, 8, 5, 1)
val c3 = DLLCombinerImplementation(4)
c3 += 1 // (1)
c1.combine(c2).combine(c3) // (7, 2, 4, 3) <-> (9, 5, 1) <-> (6, 8, 5, 1) <-> (1)
val res = c1.result() // (7, 2, 4, 3, 9, 5, 1, 6, 8, 5, 1, 1)
```
You can look at the public tests to find more examples.
In your solution you should only make changes to the `DLLCombinerImplementation` class. You are not allowed to change the file `lib.scala`. You can get partial points for solving parts of this exercise.