System and method to quantify digital data sharing in a multi-threaded execution

Patent metadata

Field	Value
Publication number	US-9535704-B2
Application number	US-201514613066-A
Country	US
Kind code	B2
Filing date	Feb 3, 2015
Priority date	Feb 3, 2014
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

A method to quantify a plurality of digital data sharing in a multi-threaded execution includes the steps of: providing at least one processor; providing a computer readable non-transitory storage medium including a computer readable multi-threaded executable code and a computer readable executable code to calculate a plurality of shared footprint values and an average shared footprint value; running the multi-threaded executable code on the at least one computer processor; running the computer readable executable code configured to calculate a plurality of shared footprint values and an average shared footprint value; calculating a plurality of shared footprint values by use of a linear-time process for a corresponding plurality of executable windows in time; and calculating and saving an average shared footprint value based on the plurality of shared footprint values to quantify by a metric the data sharing by the multi-threaded execution. A system to perform the method is also described.

First claim

What is claimed is:

1. A method to quantify a plurality of digital data sharing in a multi-threaded execution comprising the steps of:
providing a computer readable non-transitory storage medium comprising a computer readable multi-threaded executable code to run on at least one computer processor and a computer readable executable code configured to calculate a plurality of shared footprint values and an average shared footprint value;
running said multi-threaded executable code on said at least one computer processor;
running said computer readable executable code configured to calculate a plurality of shared footprint values and an average shared footprint value on said at least one computer processor or on another computer processor communicatively coupled to said at least one computer processor;
calculating a plurality of shared footprint values of data shared by a plurality of threads of a multi-threaded execution by use of a linear-time process for a corresponding plurality of executable windows in time;
calculating and saving an average shared footprint value based on said plurality of shared footprint values to quantify by a metric of said data sharing by said multi-threaded execution; and
wherein each sharer footprint comprises an equation:
sfpk +([ i, j ])=|{d ε D|d is used by at least k threads in [ i, j ]}|.

2. The method of claim 1 , wherein said multi-threaded execution comprises a trace from a multi-threaded program and each of said plurality of digital data sharing comprises a datum in a memory cell.

3. The method of claim 1 , wherein said at least one computer processor comprises at least one multi-core processor.

4. The method of claim 1 , wherein said average shared footprint comprises an average of sharer footprints.

5. The method of claim 4 , wherein said average shared footprint value comprises an equation:

sfp

k
+

_

⁡

(
l
)

=

⁢

sum
⁢

⁢
of
⁢

⁢
k

+

sharers
⁢

⁢
footprints
⁢

⁢
in
⁢

⁢
length
⁢

-

⁢
l
⁢

⁢
windows

number
⁢

⁢
of
⁢

⁢
length
⁢

-

⁢
l
⁢

⁢
windows

=

⁢

∑

i
=
1

N
-
l
+
1

⁢

sfp

k
+

⁡

(

[

i
,

i
+
l
-
1

]

)

N
-
1
+
1

.

6. The method of claim 4 , wherein said average of sharer footprints is calculated by an equation:

sfp

k
+

_

⁡

(
l
)

=

⁢



D

Assignees

• Ding Chen
• Luo Hao
• Univ Rochester

Inventors

• Ding Chen
• Luo Hao

Classifications

• G06F11/3404 Primary

  for parallel or distributed programming · CPC title

• G06F9/3863 Primary

  using multiple copies of the architectural state, e.g. shadow registers · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F9/30047

  Prefetch instructions; cache control instructions · CPC title

• G06F2201/885

  Monitoring specific for caches · CPC title