You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by ar...@apache.org on 2020/06/02 22:24:51 UTC
[systemml] branch master updated: [MINOR] Fix bugs in scoring
function and eviction logic.
This is an automated email from the ASF dual-hosted git repository.
arnabp20 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push:
new faec158 [MINOR] Fix bugs in scoring function and eviction logic.
faec158 is described below
commit faec15810e18fc497e950b830811a919f5aa5c5f
Author: arnabp <ar...@tugraz.at>
AuthorDate: Tue Jun 2 18:34:36 2020 +0200
[MINOR] Fix bugs in scoring function and eviction logic.
This patch fixes the root cause behind lineage test failure in github.
This patch
- fixes a bug in the scoring function,
- fixes double polling issue in eviction logic,
- adds APIs to control reusable opcodes from outside. This helps
anticipating and test caching and eviction behaviors,
- removes a faulty assertion from eviction test and also adds a new assertion.
---
.../org/apache/sysds/runtime/lineage/LineageCache.java | 1 +
.../apache/sysds/runtime/lineage/LineageCacheConfig.java | 15 ++++++++++++---
.../sysds/runtime/lineage/LineageCacheEviction.java | 13 ++++---------
.../sysds/runtime/lineage/LineageCacheStatistics.java | 4 ++++
.../sysds/test/functions/lineage/CacheEvictionTest.java | 10 ++++++----
src/test/scripts/functions/lineage/CacheEviction1.dml | 15 ++++++++-------
6 files changed, 35 insertions(+), 23 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
index ca6b349..9f53395 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
@@ -342,6 +342,7 @@ public class LineageCache
// Maintain _origItem as head.
while (tmp._nextEntry != null)
tmp = tmp._nextEntry;
+ // FIXME: No need add at the end; add just after head.
tmp._nextEntry = e;
//maintain order for eviction
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
index 7fce53b..c4caed9 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
@@ -32,11 +32,12 @@ public class LineageCacheConfig
{
//-------------CACHING LOGIC RELATED CONFIGURATIONS--------------//
- private static final String[] REUSE_OPCODES = new String[] {
+ private static final String[] OPCODES = new String[] {
"tsmm", "ba+*", "*", "/", "+", "||", "nrow", "ncol", "round", "exp", "log",
"rightIndex", "leftIndex", "groupedagg", "r'", "solve", "spoof"
//TODO: Reuse everything.
};
+ private static String[] REUSE_OPCODES = new String[] {};
public enum ReuseCacheType {
REUSE_FULL,
@@ -120,7 +121,7 @@ public class LineageCacheConfig
double w2 = LineageCacheConfig.WEIGHTS[1];
// Generate scores
double score1 = w1*(((double)e1._computeTime)/e1.getSize()) + w2*e1.getTimestamp();
- double score2 = w1*((double)e2._computeTime)/e2.getSize() + w2*e1.getTimestamp();
+ double score2 = w1*((double)e2._computeTime)/e2.getSize() + w2*e2.getTimestamp();
// Generate order. If scores are same, order by LineageItem ID.
return score1 == score2 ? Long.compare(e1._key.getId(), e2._key.getId()) : score1 < score2 ? -1 : 1;
};
@@ -129,11 +130,19 @@ public class LineageCacheConfig
static {
//setup static configuration parameters
+ REUSE_OPCODES = OPCODES;
setSpill(true);
- //setCachePolicy(LineageCachePolicy.WEIGHTED);
+ setCachePolicy(LineageCachePolicy.HYBRID);
setCompAssRW(true);
}
+ public static void setReusableOpcodes(String... ops) {
+ REUSE_OPCODES = ops;
+ }
+
+ public static void resetReusableOpcodes() {
+ REUSE_OPCODES = OPCODES;
+ }
public static boolean isReusable (Instruction inst, ExecutionContext ec) {
boolean insttype = inst instanceof ComputationCPInstruction
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
index 2139689..30f930f 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
@@ -178,17 +178,16 @@ public class LineageCacheEviction
protected static void makeSpace(Map<LineageItem, LineageCacheEntry> cache, long spaceNeeded) {
//Cost based eviction
- LineageCacheEntry e = weightedQueue.pollFirst();
- while (e != null)
+ while ((spaceNeeded + _cachesize) > CACHE_LIMIT)
{
- if ((spaceNeeded + _cachesize) <= CACHE_LIMIT)
- // Enough space recovered.
+ LineageCacheEntry e = weightedQueue.pollFirst();
+ if (e == null)
+ // Nothing to evict.
break;
if (!LineageCacheConfig.isSetSpill()) {
// If eviction is disabled, just delete the entries.
removeOrSpillEntry(cache, e, false);
- e = weightedQueue.pollFirst();
continue;
}
@@ -205,7 +204,6 @@ public class LineageCacheEviction
// No spilling for scalar entries. Just delete those.
// Note: scalar entries with higher computation time are pinned.
removeOrSpillEntry(cache, e, false);
- e = weightedQueue.pollFirst();
continue;
}
@@ -239,9 +237,6 @@ public class LineageCacheEviction
else
removeOrSpillEntry(cache, e, false); //delete
}
-
- // Remove the entry from cache.
- e = weightedQueue.pollFirst();
}
}
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java
index 55bf70f..143fdfc 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java
@@ -79,6 +79,10 @@ public class LineageCacheStatistics {
// Number of times single instruction results are reused (full and partial).
_numHitsInst.increment();
}
+
+ public static long getInstHits() {
+ return _numHitsInst.longValue();
+ }
public static void incrementSBHits() {
// Number of times statementblock results are reused.
diff --git a/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java b/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java
index 9f925c5..03604e4 100644
--- a/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java
+++ b/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java
@@ -85,6 +85,7 @@ public class CacheEvictionTest extends AutomatedTestBase {
fullDMLScriptName = getScript();
Lineage.resetInternalState();
long cacheSize = LineageCacheEviction.getCacheLimit();
+ LineageCacheConfig.setReusableOpcodes("exp", "+", "round");
// LRU based eviction
List<String> proArgs = new ArrayList<>();
@@ -99,7 +100,7 @@ public class CacheEvictionTest extends AutomatedTestBase {
runTest(true, EXCEPTION_NOT_EXPECTED, null, -1);
HashMap<MatrixValue.CellIndex, Double> R_lru = readDMLMatrixFromHDFS("R");
long expCount_lru = Statistics.getCPHeavyHitterCount("exp");
- long plusCount_lru = Statistics.getCPHeavyHitterCount("+");
+ long hitCount_lru = LineageCacheStatistics.getInstHits();
long evictedCount_lru = LineageCacheStatistics.getMemDeletes();
// Weighted scheme (computationTime/Size)
@@ -116,8 +117,9 @@ public class CacheEvictionTest extends AutomatedTestBase {
runTest(true, EXCEPTION_NOT_EXPECTED, null, -1);
HashMap<MatrixValue.CellIndex, Double> R_weighted= readDMLMatrixFromHDFS("R");
long expCount_wt = Statistics.getCPHeavyHitterCount("exp");
- long plusCount_wt = Statistics.getCPHeavyHitterCount("+");
+ long hitCount_wt = LineageCacheStatistics.getInstHits();
long evictedCount_wt = LineageCacheStatistics.getMemDeletes();
+ LineageCacheConfig.resetReusableOpcodes();
// Compare results
Lineage.setLinReuseNone();
@@ -125,11 +127,11 @@ public class CacheEvictionTest extends AutomatedTestBase {
// Compare reused instructions
Assert.assertTrue(expCount_lru > expCount_wt);
- Assert.assertTrue(plusCount_lru < plusCount_wt);
-
// Compare counts of evicted items
// LRU tends to evict more entries to recover equal amount of memory
Assert.assertTrue(evictedCount_lru > evictedCount_wt);
+ // Compare cache hits
+ Assert.assertTrue(hitCount_lru < hitCount_wt);
}
finally {
OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = old_simplification;
diff --git a/src/test/scripts/functions/lineage/CacheEviction1.dml b/src/test/scripts/functions/lineage/CacheEviction1.dml
index f25ad6d..5c9b94c 100644
--- a/src/test/scripts/functions/lineage/CacheEviction1.dml
+++ b/src/test/scripts/functions/lineage/CacheEviction1.dml
@@ -19,7 +19,6 @@
#
#-------------------------------------------------------------
-
cache_size = ceil($1/(1024*1024)); #in MB
output_size = 8; #8MB
X = rand(rows=1024, cols=1024, sparsity = 1.0, seed=42);
@@ -34,17 +33,19 @@ for (i in 1:k/2) {
X = X + 1;
}
-# Trigger eviction. LRU evicts both 'exp' and '+' results,
-# where Weighted scheme evicts only '+' results to recover
+# Trigger evictions. LRU evicts half of both 'exp' and '+' results,
+# where Weighted scheme evicts all the '+' results to recover
# same amount of memory.
-for (i in 1:1.5*k/4) {
+for (i in 1:k/4) {
R = round(X);
X = X + 1;
}
-
-# Try to reuse 'exp' and '+' results. LRU reuses less
-# 'exp' outputs but more '+' outputs.
+# Try to reuse 'exp' and '+' results. LRU keeps evicting
+# the remaining half of 'exp' and '+' results from the 1st
+# loop, and in turn fails to reuse any of the instructions,
+# where Weighted scheme keeps evicting the '+'s (from 2nd loop)
+# but able to reuse 'exp's.
for (i in 1:k/4) {
R1 = exp(X1);
X1 = X1 + 1;