diff --git a/build/test_package.mk b/build/test_package.mk
index c6b0865..13e582e 100644
--- a/build/test_package.mk
+++ b/build/test_package.mk
@@ -39,6 +39,11 @@
 else
 PRIVATE_CTS_TEST_PACKAGE_NAME_ := android.$(notdir $(LOCAL_PATH))
 endif
+ifeq ($(cts_runtime_hint),)
+$(cts_package_xml): PRIVATE_CTS_RUNTIME_HINT := "0"
+else
+$(cts_package_xml): PRIVATE_CTS_RUNTIME_HINT := $(cts_runtime_hint)
+endif
 $(cts_package_xml): PRIVATE_TEST_PACKAGE := $(PRIVATE_CTS_TEST_PACKAGE_NAME_)
 $(cts_package_xml): PRIVATE_MANIFEST := $(LOCAL_PATH)/AndroidManifest.xml
 $(cts_package_xml): PRIVATE_TEST_TYPE := $(if $(LOCAL_CTS_TEST_RUNNER),$(LOCAL_CTS_TEST_RUNNER),'')
@@ -56,9 +61,13 @@
 						-i "$(PRIVATE_INSTRUMENTATION)" \
 						-n $(PRIVATE_PACKAGE) \
 						-p $(PRIVATE_TEST_PACKAGE) \
+						-x "runtimeHint->$(PRIVATE_CTS_RUNTIME_HINT)" \
 						-e $(CTS_EXPECTATIONS) \
 						-b $(CTS_UNSUPPORTED_ABIS) \
 						-a $(CTS_TARGET_ARCH) \
 						-o $@
 # Have the module name depend on the cts files; so the cts files get generated when you run mm/mmm/mma/mmma.
 $(my_register_name) : $(cts_package_xml) $(cts_module_test_config)
+
+# Make sure we clear cts_runtime_hint, so other parents will use the default if they do not set cts_runtime_hint.
+cts_runtime_hint :=
diff --git a/suite/cts/deviceTests/filesystemperf/Android.mk b/suite/cts/deviceTests/filesystemperf/Android.mk
index 843d21a..7ee93de 100644
--- a/suite/cts/deviceTests/filesystemperf/Android.mk
+++ b/suite/cts/deviceTests/filesystemperf/Android.mk
@@ -26,5 +26,7 @@
 
 LOCAL_SDK_VERSION := 16
 
+cts_runtime_hint := 28
+
 include $(BUILD_CTS_PACKAGE)
 
diff --git a/suite/cts/deviceTests/videoperf/Android.mk b/suite/cts/deviceTests/videoperf/Android.mk
index a393683..b589475 100644
--- a/suite/cts/deviceTests/videoperf/Android.mk
+++ b/suite/cts/deviceTests/videoperf/Android.mk
@@ -33,5 +33,7 @@
 
 LOCAL_SDK_VERSION := current
 
+cts_runtime_hint := 50
+
 include $(BUILD_CTS_PACKAGE)
 
diff --git a/tests/tests/hardware/Android.mk b/tests/tests/hardware/Android.mk
index 9c26d8a..07d5de9 100644
--- a/tests/tests/hardware/Android.mk
+++ b/tests/tests/hardware/Android.mk
@@ -57,4 +57,6 @@
 
 LOCAL_JAVA_LIBRARIES := android.test.runner
 
+cts_runtime_hint := 120
+
 include $(BUILD_CTS_PACKAGE)
diff --git a/tests/tests/keystore/Android.mk b/tests/tests/keystore/Android.mk
index eaf5389..e51bc04 100644
--- a/tests/tests/keystore/Android.mk
+++ b/tests/tests/keystore/Android.mk
@@ -26,6 +26,8 @@
 
 LOCAL_SDK_VERSION := current
 
+cts_runtime_hint := 28
+
 include $(BUILD_CTS_PACKAGE)
 
 include $(call all-makefiles-under,$(LOCAL_PATH))
diff --git a/tests/tests/media/Android.mk b/tests/tests/media/Android.mk
index 13daca6..ea7256d 100644
--- a/tests/tests/media/Android.mk
+++ b/tests/tests/media/Android.mk
@@ -51,6 +51,8 @@
 #LOCAL_SDK_VERSION := current
 LOCAL_JAVA_LIBRARIES += android.test.runner org.apache.http.legacy
 
+cts_runtime_hint := 265
+
 include $(BUILD_CTS_PACKAGE)
 
 include $(call all-makefiles-under,$(LOCAL_PATH))
diff --git a/tests/tests/mediastress/Android.mk b/tests/tests/mediastress/Android.mk
index 5bb23d0..d78ddac 100644
--- a/tests/tests/mediastress/Android.mk
+++ b/tests/tests/mediastress/Android.mk
@@ -33,6 +33,8 @@
 
 LOCAL_SDK_VERSION := current
 
+cts_runtime_hint := 170
+
 include $(BUILD_CTS_PACKAGE)
 
 include $(call all-makefiles-under,$(LOCAL_PATH))
diff --git a/tools/tradefed-host/.classpath b/tools/tradefed-host/.classpath
index e716219..dbeeb01 100644
--- a/tools/tradefed-host/.classpath
+++ b/tools/tradefed-host/.classpath
@@ -7,5 +7,6 @@
 	<classpathentry exported="true" kind="var" path="CTS_SRC_ROOT/out/host/common/obj/JAVA_LIBRARIES/ctsdeviceinfolib_intermediates/javalib.jar"/>
 	<classpathentry kind="var" path="CTS_SRC_ROOT/out/host/common/obj/JAVA_LIBRARIES/hosttestlib_intermediates/javalib.jar"/>
 	<classpathentry kind="var" path="CTS_SRC_ROOT/prebuilts/misc/common/tradefed/tradefed-prebuilt.jar"/>
+	<classpathentry combineaccessrules="false" kind="src" path="/cts-commonutil"/>
 	<classpathentry kind="output" path="bin"/>
 </classpath>
diff --git a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/CtsTest.java b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/CtsTest.java
index d74cce5..244f348 100644
--- a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/CtsTest.java
+++ b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/CtsTest.java
@@ -64,6 +64,7 @@
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashSet;
@@ -251,6 +252,20 @@
         }
     }
 
+
+    /**
+     * A {@link Comparator} for sorting {@link TestPackage}s by running time hint.
+     */
+    static class RuntimeHintComparator implements Comparator<TestPackage> {
+
+        @Override
+        public int compare(TestPackage left, TestPackage right) {
+            return Long.compare(left.getPackageDef().getRuntimeHint(),
+                    right.getPackageDef().getRuntimeHint());
+        }
+
+    }
+
     /**
      * A {@link ResultForwarder} that will forward a bugreport on each failed test.
      */
@@ -811,6 +826,10 @@
             int numTestPackages = testPackageList.size();
             int totalShards = Math.min(mTotalShards, numTestPackages);
 
+            // Sort test packages by running time hint, to force packages with large expected
+            // running times to different shards if possible.
+            Collections.sort(testPackageList, new RuntimeHintComparator());
+
             List<TestPackage> shardTestPackageList = new ArrayList<>();
             for (int i = mShardAssignment; i < numTestPackages; i += totalShards) {
                 shardTestPackageList.add(testPackageList.get(i));
diff --git a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/ITestPackageDef.java b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/ITestPackageDef.java
index 13f3572..630dee3 100644
--- a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/ITestPackageDef.java
+++ b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/ITestPackageDef.java
@@ -72,6 +72,11 @@
     public IAbi getAbi();
 
     /**
+     * @return the estimated running time of this test package.
+     */
+    public long getRuntimeHint();
+
+    /**
      * Set the filter to use for tests
      *
      * @param testFilter
diff --git a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageDef.java b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageDef.java
index 12c3ddd..d08c0bc 100644
--- a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageDef.java
+++ b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageDef.java
@@ -66,6 +66,7 @@
     private String mRunTimeArgs = null;
     private String mTestPackageName = null;
     private String mDigest = null;
+    private long mRuntimeHint = 0;
     private IAbi mAbi = null;
     private List<ITargetPreparer> mPreparers = null;
 
@@ -137,6 +138,18 @@
      * {@inheritDoc}
      */
     @Override
+    public long getRuntimeHint() {
+        return mRuntimeHint;
+    }
+
+    void setRuntimeHint(long runtimeHint) {
+        mRuntimeHint = runtimeHint;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
     public String getName() {
         return mName;
     }
diff --git a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageXmlParser.java b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageXmlParser.java
index 649dd9e..951c461 100644
--- a/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageXmlParser.java
+++ b/tools/tradefed-host/src/com/android/cts/tradefed/testtype/TestPackageXmlParser.java
@@ -86,6 +86,10 @@
                 final String targetNameSpace = attributes.getValue("targetNameSpace");
                 final String runTimeArgs = attributes.getValue("runtimeArgs");
                 final String testType = getTestType(attributes);
+                long runTimeHint = 0;
+                if (attributes.getValue("runtimeHint") != null) {
+                    runTimeHint = Long.parseLong(attributes.getValue("runtimeHint"));
+                }
 
                 for (String abiName : AbiUtils.getAbisSupportedByCts()) {
                     Abi abi = new Abi(abiName, AbiUtils.getBitness(abiName));
@@ -102,6 +106,7 @@
                     }
                     packageDef.setTargetBinaryName(targetBinaryName);
                     packageDef.setTargetNameSpace(targetNameSpace);
+                    packageDef.setRuntimeHint(runTimeHint);
                     packageDef.setAbi(abi);
                     mPackageDefs.put(abiName, packageDef);
                 }