Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-01

AUTHORS

Min Li, Chao Yang, Qiao Sun, Wen-Jing Ma, Wen-Long Cao, Yu-Long Ao

ABSTRACT

With the advent of the big data era, the amounts of sampling data and the dimensions of data features are rapidly growing. It is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering, the k-means operation is receiving increasingly more attentions today. To achieve high performance k-means computations on modern multi-core/many-core systems, we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids reduction. We implement and optimize the parallel k-means algorithm on the SW26010 many-core processor, which is the major horsepower of Sunway TaihuLight. In particular, we design a task mapping strategy for load-balanced task distribution, a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data locality. Optimization techniques such as instruction reordering and double buffering are further applied to improve the sustained performance. Discussions on block-size tuning and performance modeling are also presented. We show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops, which is 46.9% of the peak performance and 84% of the theoretical performance upper bound on a single core group, and can achieve a nearly ideal scalability to the whole SW26010 processor of four core groups. Performance comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel. More... »

PAGES

77-93

References to SciGraph publications

  • 2014-08. Introducing and Implementing the Allpairs Skeleton for Programming Multi-GPU Systems in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 2009. Parallel K-Means Clustering Based on MapReduce in CLOUD COMPUTING
  • 2014-08. High performance parallel k-means clustering for disk-resident datasets on multi-core CPUs in THE JOURNAL OF SUPERCOMPUTING
  • 2014. An Efficient K-means Clustering Algorithm on MapReduce in DATABASE SYSTEMS FOR ADVANCED APPLICATIONS
  • 2010. Human Activity Recognition Using Inertial/Magnetic Sensor Units in HUMAN BEHAVIOR UNDERSTANDING
  • 2002-05-17. A Data-Clustering Algorithm on Distributed Memory Multiprocessors in LARGE-SCALE PARALLEL DATA MINING
  • 2013. A Vectorized K-Means Algorithm for Intel Many Integrated Core Architecture in ADVANCED PARALLEL PROCESSING TECHNOLOGIES
  • 2016-07. The Sunway TaihuLight supercomputer: system and applications in SCIENCE CHINA INFORMATION SCIENCES
  • 2008-01. Top 10 algorithms in data mining in KNOWLEDGE AND INFORMATION SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11390-019-1900-5

    DOI

    http://dx.doi.org/10.1007/s11390-019-1900-5

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1111665002


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Chinese Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.410726.6", 
              "name": [
                "Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China", 
                "University of Chinese Academy of Sciences, 100049, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Li", 
            "givenName": "Min", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Peking University", 
              "id": "https://www.grid.ac/institutes/grid.11135.37", 
              "name": [
                "School of Mathematical Sciences, Peking University, 100871, Beijing, China", 
                "Center for Data Science, Peking University, 100871, Beijing, China", 
                "Peng Cheng Laboratory, 518052, Shenzhen, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Chao", 
            "id": "sg:person.014157663040.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157663040.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Software", 
              "id": "https://www.grid.ac/institutes/grid.458446.f", 
              "name": [
                "Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sun", 
            "givenName": "Qiao", 
            "id": "sg:person.011224664663.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011224664663.07"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Software", 
              "id": "https://www.grid.ac/institutes/grid.458446.f", 
              "name": [
                "Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ma", 
            "givenName": "Wen-Jing", 
            "id": "sg:person.016577553405.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016577553405.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Chinese Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.410726.6", 
              "name": [
                "Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China", 
                "University of Chinese Academy of Sciences, 100049, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cao", 
            "givenName": "Wen-Long", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Peking University", 
              "id": "https://www.grid.ac/institutes/grid.11135.37", 
              "name": [
                "School of Mathematical Sciences, Peking University, 100871, Beijing, China", 
                "Center for Data Science, Peking University, 100871, Beijing, China", 
                "Peng Cheng Laboratory, 518052, Shenzhen, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ao", 
            "givenName": "Yu-Long", 
            "id": "sg:person.011671623345.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011671623345.77"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/2964910", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003941035"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2020408.2020516", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004681766"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-45293-2_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008838531", 
              "https://doi.org/10.1007/978-3-642-45293-2_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.parco.2013.01.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011118357"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-05810-8_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019926392", 
              "https://doi.org/10.1007/978-3-319-05810-8_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/584792.584890", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023653823"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.5194/gi-4-121-2015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028066104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2012.05.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030184251"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10115-007-0114-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032043586", 
              "https://doi.org/10.1007/s10115-007-0114-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10115-007-0114-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032043586", 
              "https://doi.org/10.1007/s10115-007-0114-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10766-013-0265-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034948126", 
              "https://doi.org/10.1007/s10766-013-0265-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46502-2_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035721413", 
              "https://doi.org/10.1007/3-540-46502-2_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46502-2_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035721413", 
              "https://doi.org/10.1007/3-540-46502-2_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14715-9_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035987277", 
              "https://doi.org/10.1007/978-3-642-14715-9_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14715-9_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035987277", 
              "https://doi.org/10.1007/978-3-642-14715-9_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.patcog.2010.04.019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038580140"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jpdc.2008.05.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041594073"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/77626.79170", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042853901"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1531666.1531668", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043655877"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11227-014-1185-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044628591", 
              "https://doi.org/10.1007/s11227-014-1185-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10665-1_71", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047084385", 
              "https://doi.org/10.1007/978-3-642-10665-1_71"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10665-1_71", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047084385", 
              "https://doi.org/10.1007/978-3-642-10665-1_71"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11432-016-5588-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050885772", 
              "https://doi.org/10.1007/s11432-016-5588-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11432-016-5588-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050885772", 
              "https://doi.org/10.1007/s11432-016-5588-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/bxt075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059480558"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1982.1056488", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061648676"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpami.2014.2321376", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061744673"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2010.65", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753659"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2012.234", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061754041"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/embc.2013.6610858", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1078797600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/iiswc.2006.302743", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093200354"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sc.2016.5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093366955"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2011.102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093411341"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icpp.2017.51", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093715444"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2015.117", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093838469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sc.2016.3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093865451"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/pdp.2011.91", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093925908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/csse.2008.1018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094246577"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2011.331", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094852614"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cvpr.2016.521", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094925029"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/clusterwksp.2010.5613079", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094963032"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2017.20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095023686"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/fpl.2012.6339141", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095035966"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/fpl.2013.6645501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095145814"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/intensive.2009.19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095154322"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/jcsse.2012.6261977", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095516671"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/hipc.2011.6152713", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095733756"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-01", 
        "datePublishedReg": "2019-01-01", 
        "description": "With the advent of the big data era, the amounts of sampling data and the dimensions of data features are rapidly growing. It is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering, the k-means operation is receiving increasingly more attentions today. To achieve high performance k-means computations on modern multi-core/many-core systems, we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids reduction. We implement and optimize the parallel k-means algorithm on the SW26010 many-core processor, which is the major horsepower of Sunway TaihuLight. In particular, we design a task mapping strategy for load-balanced task distribution, a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data locality. Optimization techniques such as instruction reordering and double buffering are further applied to improve the sustained performance. Discussions on block-size tuning and performance modeling are also presented. We show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops, which is 46.9% of the peak performance and 84% of the theoretical performance upper bound on a single core group, and can achieve a nearly ideal scalability to the whole SW26010 processor of four core groups. Performance comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s11390-019-1900-5", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1320078", 
            "issn": [
              "1666-6046", 
              "1666-6038"
            ], 
            "name": "Journal of Computer Science and Technology", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "34"
          }
        ], 
        "name": "Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight", 
        "pagination": "77-93", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0306ad94b9393bedb3df524f0359688f929e8dc1411b667beb7e7894d425537f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11390-019-1900-5"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1111665002"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11390-019-1900-5", 
          "https://app.dimensions.ai/details/publication/pub.1111665002"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T08:57", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100815_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs11390-019-1900-5"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s11390-019-1900-5'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s11390-019-1900-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11390-019-1900-5'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11390-019-1900-5'


     

    This table displays all metadata directly associated to this object as RDF triples.

    238 TRIPLES      21 PREDICATES      69 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11390-019-1900-5 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N205a45e9d7d64947a07e2377c056aefd
    4 schema:citation sg:pub.10.1007/3-540-46502-2_13
    5 sg:pub.10.1007/978-3-319-05810-8_24
    6 sg:pub.10.1007/978-3-642-10665-1_71
    7 sg:pub.10.1007/978-3-642-14715-9_5
    8 sg:pub.10.1007/978-3-642-45293-2_21
    9 sg:pub.10.1007/s10115-007-0114-2
    10 sg:pub.10.1007/s10766-013-0265-6
    11 sg:pub.10.1007/s11227-014-1185-y
    12 sg:pub.10.1007/s11432-016-5588-7
    13 https://doi.org/10.1016/j.jcss.2012.05.004
    14 https://doi.org/10.1016/j.jpdc.2008.05.014
    15 https://doi.org/10.1016/j.parco.2013.01.002
    16 https://doi.org/10.1016/j.patcog.2010.04.019
    17 https://doi.org/10.1093/comjnl/bxt075
    18 https://doi.org/10.1109/clusterwksp.2010.5613079
    19 https://doi.org/10.1109/csse.2008.1018
    20 https://doi.org/10.1109/cvpr.2016.521
    21 https://doi.org/10.1109/embc.2013.6610858
    22 https://doi.org/10.1109/fpl.2012.6339141
    23 https://doi.org/10.1109/fpl.2013.6645501
    24 https://doi.org/10.1109/hipc.2011.6152713
    25 https://doi.org/10.1109/icpp.2017.51
    26 https://doi.org/10.1109/iiswc.2006.302743
    27 https://doi.org/10.1109/intensive.2009.19
    28 https://doi.org/10.1109/ipdps.2011.102
    29 https://doi.org/10.1109/ipdps.2011.331
    30 https://doi.org/10.1109/ipdps.2015.117
    31 https://doi.org/10.1109/ipdps.2017.20
    32 https://doi.org/10.1109/jcsse.2012.6261977
    33 https://doi.org/10.1109/pdp.2011.91
    34 https://doi.org/10.1109/sc.2016.3
    35 https://doi.org/10.1109/sc.2016.5
    36 https://doi.org/10.1109/tit.1982.1056488
    37 https://doi.org/10.1109/tpami.2014.2321376
    38 https://doi.org/10.1109/tpds.2010.65
    39 https://doi.org/10.1109/tpds.2012.234
    40 https://doi.org/10.1145/1531666.1531668
    41 https://doi.org/10.1145/2020408.2020516
    42 https://doi.org/10.1145/2964910
    43 https://doi.org/10.1145/584792.584890
    44 https://doi.org/10.1145/77626.79170
    45 https://doi.org/10.5194/gi-4-121-2015
    46 schema:datePublished 2019-01
    47 schema:datePublishedReg 2019-01-01
    48 schema:description With the advent of the big data era, the amounts of sampling data and the dimensions of data features are rapidly growing. It is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering, the k-means operation is receiving increasingly more attentions today. To achieve high performance k-means computations on modern multi-core/many-core systems, we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids reduction. We implement and optimize the parallel k-means algorithm on the SW26010 many-core processor, which is the major horsepower of Sunway TaihuLight. In particular, we design a task mapping strategy for load-balanced task distribution, a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data locality. Optimization techniques such as instruction reordering and double buffering are further applied to improve the sustained performance. Discussions on block-size tuning and performance modeling are also presented. We show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops, which is 46.9% of the peak performance and 84% of the theoretical performance upper bound on a single core group, and can achieve a nearly ideal scalability to the whole SW26010 processor of four core groups. Performance comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel.
    49 schema:genre research_article
    50 schema:inLanguage en
    51 schema:isAccessibleForFree false
    52 schema:isPartOf N31b066e6f8cf4adbba26cdd67c5e6379
    53 Nae863699e62b459aa3b7e7f7e67040b1
    54 sg:journal.1320078
    55 schema:name Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight
    56 schema:pagination 77-93
    57 schema:productId N2e7101b9b1df4d508420abd7b0497380
    58 N50eb54c39655494fb5f8e8e889ce1626
    59 Nf0d9b007736348e3ae9a322c5ec663e0
    60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111665002
    61 https://doi.org/10.1007/s11390-019-1900-5
    62 schema:sdDatePublished 2019-04-11T08:57
    63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    64 schema:sdPublisher Ne1746c27b45244cb8d6b070b809a1dcd
    65 schema:url https://link.springer.com/10.1007%2Fs11390-019-1900-5
    66 sgo:license sg:explorer/license/
    67 sgo:sdDataset articles
    68 rdf:type schema:ScholarlyArticle
    69 N205a45e9d7d64947a07e2377c056aefd rdf:first Nfafc50b387d045ada965aa7a98aae61e
    70 rdf:rest Nfa8dbd9d32d5444a8a64a8a2c6446219
    71 N2e7101b9b1df4d508420abd7b0497380 schema:name dimensions_id
    72 schema:value pub.1111665002
    73 rdf:type schema:PropertyValue
    74 N31b066e6f8cf4adbba26cdd67c5e6379 schema:volumeNumber 34
    75 rdf:type schema:PublicationVolume
    76 N3da901503a9e4193a3c438b8df70a44f schema:affiliation https://www.grid.ac/institutes/grid.410726.6
    77 schema:familyName Cao
    78 schema:givenName Wen-Long
    79 rdf:type schema:Person
    80 N4981d7e4e45d49a3a1706613b498c8fe rdf:first sg:person.011671623345.77
    81 rdf:rest rdf:nil
    82 N50eb54c39655494fb5f8e8e889ce1626 schema:name doi
    83 schema:value 10.1007/s11390-019-1900-5
    84 rdf:type schema:PropertyValue
    85 Na9bd564769714eaca1de8f76abaf58da rdf:first N3da901503a9e4193a3c438b8df70a44f
    86 rdf:rest N4981d7e4e45d49a3a1706613b498c8fe
    87 Nae863699e62b459aa3b7e7f7e67040b1 schema:issueNumber 1
    88 rdf:type schema:PublicationIssue
    89 Nb0cfcdb3cba943f496ad87a4c72bd35d rdf:first sg:person.011224664663.07
    90 rdf:rest Nde74be1665aa400980df6c33f86a6066
    91 Nde74be1665aa400980df6c33f86a6066 rdf:first sg:person.016577553405.08
    92 rdf:rest Na9bd564769714eaca1de8f76abaf58da
    93 Ne1746c27b45244cb8d6b070b809a1dcd schema:name Springer Nature - SN SciGraph project
    94 rdf:type schema:Organization
    95 Nf0d9b007736348e3ae9a322c5ec663e0 schema:name readcube_id
    96 schema:value 0306ad94b9393bedb3df524f0359688f929e8dc1411b667beb7e7894d425537f
    97 rdf:type schema:PropertyValue
    98 Nfa8dbd9d32d5444a8a64a8a2c6446219 rdf:first sg:person.014157663040.78
    99 rdf:rest Nb0cfcdb3cba943f496ad87a4c72bd35d
    100 Nfafc50b387d045ada965aa7a98aae61e schema:affiliation https://www.grid.ac/institutes/grid.410726.6
    101 schema:familyName Li
    102 schema:givenName Min
    103 rdf:type schema:Person
    104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    105 schema:name Information and Computing Sciences
    106 rdf:type schema:DefinedTerm
    107 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    108 schema:name Information Systems
    109 rdf:type schema:DefinedTerm
    110 sg:journal.1320078 schema:issn 1666-6038
    111 1666-6046
    112 schema:name Journal of Computer Science and Technology
    113 rdf:type schema:Periodical
    114 sg:person.011224664663.07 schema:affiliation https://www.grid.ac/institutes/grid.458446.f
    115 schema:familyName Sun
    116 schema:givenName Qiao
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011224664663.07
    118 rdf:type schema:Person
    119 sg:person.011671623345.77 schema:affiliation https://www.grid.ac/institutes/grid.11135.37
    120 schema:familyName Ao
    121 schema:givenName Yu-Long
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011671623345.77
    123 rdf:type schema:Person
    124 sg:person.014157663040.78 schema:affiliation https://www.grid.ac/institutes/grid.11135.37
    125 schema:familyName Yang
    126 schema:givenName Chao
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157663040.78
    128 rdf:type schema:Person
    129 sg:person.016577553405.08 schema:affiliation https://www.grid.ac/institutes/grid.458446.f
    130 schema:familyName Ma
    131 schema:givenName Wen-Jing
    132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016577553405.08
    133 rdf:type schema:Person
    134 sg:pub.10.1007/3-540-46502-2_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035721413
    135 https://doi.org/10.1007/3-540-46502-2_13
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/978-3-319-05810-8_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019926392
    138 https://doi.org/10.1007/978-3-319-05810-8_24
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-642-10665-1_71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047084385
    141 https://doi.org/10.1007/978-3-642-10665-1_71
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-642-14715-9_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035987277
    144 https://doi.org/10.1007/978-3-642-14715-9_5
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-642-45293-2_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008838531
    147 https://doi.org/10.1007/978-3-642-45293-2_21
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s10115-007-0114-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032043586
    150 https://doi.org/10.1007/s10115-007-0114-2
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/s10766-013-0265-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034948126
    153 https://doi.org/10.1007/s10766-013-0265-6
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/s11227-014-1185-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1044628591
    156 https://doi.org/10.1007/s11227-014-1185-y
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/s11432-016-5588-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050885772
    159 https://doi.org/10.1007/s11432-016-5588-7
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1016/j.jcss.2012.05.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030184251
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1016/j.jpdc.2008.05.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041594073
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/j.parco.2013.01.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011118357
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1016/j.patcog.2010.04.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038580140
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1093/comjnl/bxt075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059480558
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1109/clusterwksp.2010.5613079 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094963032
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1109/csse.2008.1018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094246577
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1109/cvpr.2016.521 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094925029
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1109/embc.2013.6610858 schema:sameAs https://app.dimensions.ai/details/publication/pub.1078797600
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1109/fpl.2012.6339141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095035966
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1109/fpl.2013.6645501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095145814
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1109/hipc.2011.6152713 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095733756
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1109/icpp.2017.51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093715444
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1109/iiswc.2006.302743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093200354
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1109/intensive.2009.19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095154322
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1109/ipdps.2011.102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093411341
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1109/ipdps.2011.331 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094852614
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1109/ipdps.2015.117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093838469
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1109/ipdps.2017.20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095023686
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1109/jcsse.2012.6261977 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095516671
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1109/pdp.2011.91 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093925908
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1109/sc.2016.3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093865451
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1109/sc.2016.5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093366955
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1109/tit.1982.1056488 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061648676
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1109/tpami.2014.2321376 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061744673
    210 rdf:type schema:CreativeWork
    211 https://doi.org/10.1109/tpds.2010.65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753659
    212 rdf:type schema:CreativeWork
    213 https://doi.org/10.1109/tpds.2012.234 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061754041
    214 rdf:type schema:CreativeWork
    215 https://doi.org/10.1145/1531666.1531668 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043655877
    216 rdf:type schema:CreativeWork
    217 https://doi.org/10.1145/2020408.2020516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004681766
    218 rdf:type schema:CreativeWork
    219 https://doi.org/10.1145/2964910 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003941035
    220 rdf:type schema:CreativeWork
    221 https://doi.org/10.1145/584792.584890 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023653823
    222 rdf:type schema:CreativeWork
    223 https://doi.org/10.1145/77626.79170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042853901
    224 rdf:type schema:CreativeWork
    225 https://doi.org/10.5194/gi-4-121-2015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028066104
    226 rdf:type schema:CreativeWork
    227 https://www.grid.ac/institutes/grid.11135.37 schema:alternateName Peking University
    228 schema:name Center for Data Science, Peking University, 100871, Beijing, China
    229 Peng Cheng Laboratory, 518052, Shenzhen, China
    230 School of Mathematical Sciences, Peking University, 100871, Beijing, China
    231 rdf:type schema:Organization
    232 https://www.grid.ac/institutes/grid.410726.6 schema:alternateName University of Chinese Academy of Sciences
    233 schema:name Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China
    234 University of Chinese Academy of Sciences, 100049, Beijing, China
    235 rdf:type schema:Organization
    236 https://www.grid.ac/institutes/grid.458446.f schema:alternateName Institute of Software
    237 schema:name Institute of Software, Chinese Academy of Sciences, 100190, Beijing, China
    238 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...