東京大学 情報理工学系研究科 創造情報学専攻 2017年8月実施 プログラミング
Author
Description
Assume that matrix elements are non-negative integers and they are stored in main memory.
(1) When the algorithm below is used to multiply an
Reading the same element twice is considered as two operations.
Do not count accesses to matrix
var i = 0
while i < m begin
var j = 0
while j < m begin
var d = 0
var k = 0
while k < n begin
d = d + a[i, k] * b[k, j]
k = k + 1
end
c[i, j] = d
j = j + 1
end
i = i + 1
end
(2) When an
is written into a file as follows:
0 1 2 3, 4 5 6 7, 8 9 10 11.
Answer the numbers of rows and columns in the matrix stored in file mat1.txt in the USB flash drive.
Write the answer in your answer sheet. Ignore all letters following a period in the file.
(3) Compute the trace (the sum of the main diagonal elements) of the product of the matrices mat1.txt and mat2.txt in the USB flash drive.
Write the answer in your answer sheet.
(4) Once an element of a matrix is read from the main memory, it is saved in cache memory, and when the same element is required, the element is not read from the main memory as long as it is saved in the cache memory.
The cache memory can hold at most
Under this circumstance, how many times are the elements of
(5) Suppose that
var u = 0
while u < m begin
var v = 0
while v < m begin
var w = 0
while w < n begin
var i = u
while i < [blank 1] + [blank 2] begin
var j = v
while j < [blank 3] + [blank 4] begin
var d = 0
var k = w
while k < [blank 5] + [blank 6] begin
d = d + a[i, k] * b[k, j]
k = k + 1
end
c[i, j] = c[i, j] + d
j = j + 1
end
i = i + 1
end
w = w + p
end
v = v + p
end
u = u + p
end
(6) How many times are matrix elements in
(7) When computing matrix multiplication as in (6), which common divider
Kai
Please click here for the sample data files.
(1)
Read access to the elements in
Elements: reads Elements: reads
Therefore, in total there are
(2)
# Here I assume that file can be weirdly formatted and matrix isn't defined in a single line.
def main():
lines = []
with open('2018-Summer/mat1.txt','r') as f:
lines = f.readlines()
rows = 0
cols = 0
cols_check = True
rows_check = True
for l in lines:
sep_cnt = l.count(',')
end_cnt = l.count('.')
if sep_cnt > 0:
rows += sep_cnt
if cols_check:
if l.find(',') > 0:
cols += len(l[:l.find(',')].strip().split(' '))
cols_check = False
else:
if cols_check:
cols += len(l.strip().split(' '))
if end_cnt > 0:
rows += 1
break
print(f"{rows} x {cols}")
if __name__ == "__main__":
main()
(3)
# Here I assume matrix defined in a single line, so one line per matrix
from locale import atoi
import numpy as np
def get_mat_from_file(filename):
mats = []
lines = []
with open(filename, 'r') as f:
lines = f.readlines()
for l in lines:
rows = l.strip()[:-1].split(',')
_r = len(rows)
_c = len(rows[0].split(' '))
mats.append(np.full((_r,_c),0))
i = 0
for ro in rows:
j = 0
for itm in ro.split(' '):
mats[-1][i,j] = atoi(itm)
j += 1
i += 1
return mats
def get_mul_mat_a_b(mat_a, mat_b):
mat_c = np.matmul(mat_a,mat_b)
return mat_c
def get_trace_for_mat(mat):
return np.trace(mat)
def main():
# According to the instructions there is no issues with using numpy
mat_a = get_mat_from_file('2018-Summer/mat1.txt')[0]
mat_b = get_mat_from_file('2018-Summer/mat2.txt')[0]
mat_c = get_mul_mat_a_b(mat_a,mat_b)
trc = get_trace_for_mat(mat_c)
print(trc)
if __name__ == "__main__":
main()
(4)
def lru_insert(elm, lru, s):
if len(lru) >= s:
lru.pop()
lru.insert(0,elm)
def lru_is_in(elm, lru):
return elm in lru
def lru_refresh(elm,lru):
lru.remove(elm)
lru.insert(0,elm)
def main():
cache_lru = []
m = 6
n = 4
s = 2
rds = 0 # number of readings
i = 0
while i < m:
j = 0
while j < m:
k = 0
while k < n:
if not lru_is_in((i+1)*n+k, cache_lru):
rds += 1
lru_insert((i+1)*n+k, cache_lru,s)
else:
lru_refresh((i+1)*n+k, cache_lru)
if not lru_is_in(-(k+1)*m-j, cache_lru):
rds += 1
lru_insert(-(k+1)*m-j, cache_lru,s)
else:
lru_refresh(-(k+1)*m-j, cache_lru)
k += 1
j += 1
i += 1
print(rds)
if __name__ == "__main__":
main()
(5)
[blank 1]- u[blank 2]- p[blank 3]- v[blank 4]- p[blank 5]- w[blank 6]- p
(6)
def lru_insert(elm, lru, s):
if len(lru) >= s:
lru.pop()
lru.insert(0,elm)
def lru_is_in(elm, lru):
return elm in lru
def lru_refresh(elm,lru):
lru.remove(elm)
lru.insert(0,elm)
def main():
cache_lru = []
m = 6
n = 4
p = 2
s = 8
rds = 0 # number of readings
u = 0
while u < m:
v = 0
while v < m:
w = 0
while w < n:
i = u
while i < u+p:
j = v
while j < v+p:
k = w
while k < w+p:
if not lru_is_in((i+1)*n+k, cache_lru):
rds += 1
lru_insert((i+1)*n+k, cache_lru,s)
else:
lru_refresh((i+1)*n+k, cache_lru)
if not lru_is_in(-(k+1)*m-j, cache_lru):
rds += 1
lru_insert(-(k+1)*m-j, cache_lru,s)
else:
lru_refresh(-(k+1)*m-j, cache_lru)
k += 1
j += 1
i += 1
w += p
v += p
u += p
print(rds)
if __name__ == "__main__":
main()
(7)
import math
def lru_insert(elm, lru, s):
if len(lru) >= s:
lru.pop()
lru.insert(0,elm)
def lru_is_in(elm, lru):
return elm in lru
def lru_refresh(elm,lru):
lru.remove(elm)
lru.insert(0,elm)
def get_p_options(m,n,s):
return [x for x in range(2,int(math.sqrt(s/2))+1) if m % x == 0 and n % x == 0]
'''
Technically, it is enough to return the number of reads for the largest p suggestion.
Since if the entire sub-matrix cannot fit into s then there there will be much more reads.
But here I am checking all posiibilities.
'''
def main():
cache_lru = []
m = 200
n = 150
s = 600
best_p = 1
min_rds = m*n*m*2
all_p = get_p_options(m,n,s)
all_p.reverse()
for p in all_p:
rds = 0 # number of readings
go_on = True
u = 0
while u < m and go_on:
v = 0
while v < m and go_on:
w = 0
while w < n and go_on:
i = u
while i < u+p and go_on:
j = v
while j < v+p and go_on:
k = w
while k < w+p and go_on:
if not lru_is_in((i+1)*n+k, cache_lru):
rds += 1
lru_insert((i+1)*n+k, cache_lru,s)
else:
lru_refresh((i+1)*n+k, cache_lru)
if not lru_is_in(-(k+1)*m-j, cache_lru):
rds += 1
lru_insert(-(k+1)*m-j, cache_lru,s)
else:
lru_refresh(-(k+1)*m-j, cache_lru)
if rds > min_rds:
go_on = False
k += 1
j += 1
i += 1
w += p
v += p
u += p
if rds < min_rds and p > best_p:
best_p = p
min_rds = rds
print(f"best p={best_p} : {min_rds} readings")
if __name__ == "__main__":
main()