[Subject Prev][Subject Next][Thread Prev][Thread Next][Date Index][Thread Index]

[hts-users:02298] Re: Fast & memory efficient HHEd clustering patch


Hi,

Heiga Zen (Byung Ha CHUN) wrote:

The attached patch code provides additional parallelization based on OpenMP to reduce the computational time while setting the Question x Model table. To turn on this parallelization, you need to compile it with a option for OpenMP. For gcc (>=4.1), please use -fopenmp option. Intel compiler also supports OpenMP (-openmp).

I made a further modification to reduce the computational cost of decision tree-based context clustering. The main modification is that the new one performs pattern matching only for unique patterns in all questions. As you know, the number of unique patterns in questions are much smaller than total number of patterns in questions. Because the new one performs pattern matching for unique patterns only, it is much faster to create the bit table between model name and questions, which is used in the decision tree-based context clustering.

Again, this patch code may have bugs. Please test it and check whether it works or not. If you find any problems in this, please report them to the hts-users ML. I hope this modification improves the scalability of HTS. It is my pleasure that this patch code contributes the further progress of both HTS itself and HTS community.

Note that the attached patch code includes my previous patch codes (hts-users:01795 & hts-users:01875) and the new one still includes OpenMP directive so it can be parallelized on a machine with multiple CPUs. Please refer to hts-users:01875 for details to use OpenMP.

Best regards,

Heiga ZEN (Byung Ha CHUN)

--
--------------------------
Heiga ZEN (Byung Ha CHUN)
Speech Technology Group
Cambridge Research Lab
Toshiba Research Europe
phone: +44 1223 436975


______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email ______________________________________________________________________
--- HHEd.c	2008-08-07 13:36:19.341080000 +0000
+++ HHEd.c	2009-11-26 16:48:07.000000000 +0000
@@ -191,7 +191,7 @@
 static float MDLfactor = 1.0;                 /* MDL control factor */
 static Boolean ignoreStrW = FALSE;            /* ignore stream weight */
 static float minVar = 1.0E-6;                 /* minimum variance for clusterd item */
-static Boolean reduceMem = FALSE;             /* reduce memory requirement for decision-tree clustering */
+static int reduceMem = 0;                     /* reduce memory requirement for decision-tree clustering (0: no reduction, 1: mid reduction but fast, 2: large reduction but slow */
 static float minLeafOcc = 0.0;                /* minimum occ for each leaf node */
 static float minMixOcc = 0.0;                 /* minimum occ for each mix */
 static Vector shrinkOccThresh=NULL;           /* occupancy threshold for shrinking decision trees */
@@ -216,7 +216,7 @@
       if (GetConfBool(cParm,nParm,"SINGLETREE",&b)) singleTree = b;
       if (GetConfBool(cParm,nParm,"APPLYMDL",&b)) applyMDL = b;
       if (GetConfBool(cParm,nParm,"IGNORESTRW",&b)) ignoreStrW = b;
-      if (GetConfBool(cParm,nParm,"REDUCEMEM",&b)) reduceMem = b;
+      if (GetConfInt(cParm,nParm,"REDUCEMEM",&i)) reduceMem = i;
       if (GetConfFlt(cParm,nParm,"MINVAR",&f)) minVar = f;
       if (GetConfFlt(cParm,nParm,"MDLFACTOR",&f)) MDLfactor = f;
       if (GetConfFlt(cParm,nParm,"MINLEAFOCC",&f)) minLeafOcc = f;
@@ -306,7 +306,10 @@
    printf(" -m      apply MDL principle for clustering                off\n");
    printf(" -o s    extension for new hmm files          as source\n");
    printf(" -p      use pattern instead of base phone                 off\n");
-   printf(" -r      reduce memory usage on clustering                 off\n");
+   printf(" -r n    reduce memory usage on clustering                 0\n");
+   printf("          0: no memory reduction                           \n");
+   printf("          1: mid reduction but fast                        \n");
+   printf("          2: large reduction but slow                      \n");
    printf(" -s      construct single tree                             off\n");
    printf(" -v f    Set minimum variance to f                         1.0E-6\n");
    printf(" -w mmf  Save all HMMs to macro file mmf s    as source\n");
@@ -363,7 +366,7 @@
       case 'p':
          usePattern = TRUE; break;
       case 'r':
-         reduceMem = TRUE; break;
+         reduceMem = GetChkedInt(0,2,s); break;
       case 's':
          singleTree = TRUE; break;
       case 'v':
@@ -475,30 +478,37 @@
 
 /* ------------- Question Handling for Tree Building ----------- */
 
-typedef struct _IPat{
+static int nQuestions=0;
+static int nPatterns=0;
+static char **QMTable=NULL;
+static Boolean setQMTable=FALSE;
+
+typedef struct {
    char *pat;
-   struct _IPat *next;
+   int index;
 }IPat;
 
 typedef struct _Question{      /* each question stored as both pattern and  */
    LabId qName;                 /* an expanded list of model names */
-   IPat *patList;               
+   ILink patList;
    ILink ilist;
    char pattern[PAT_LEN];
+   int index;
    Boolean used;
 } Question;
 
+static ILink pList = NULL;      /* pattern list */
 static ILink qList = NULL;      /* question list */
 
 /* TraceQuestion: output given questions */
 void TraceQuestion(char *cmd, Question *q)
 {
-   IPat *ip;
+   ILink ip;
    
    printf("   %s %s: defines %d % d models\n       ",
           cmd,q->qName->name,NumItems(q->ilist),hset->numLogHMM);
    for (ip=q->patList; ip!=NULL; ip=ip->next)
-      printf("%s ",ip->pat); 
+      printf("%s ", ((IPat *)ip->item)->pat); 
    printf("\n");
    fflush(stdout);
 }
@@ -541,10 +551,11 @@
 }
 
 /* ParsePattern: parse given string and return pattern list */
-IPat *ParsePattern (char *pattern)
+void ParsePattern (ILink *patList, char *pattern)
 {
    char *p,*r,buf[PAT_LEN];
    IPat *ip=NULL, *ipat=NULL;
+   ILink i;
    
    for (p=pattern;*p && isspace((int) *p);p++);
    
@@ -569,13 +580,23 @@
       if (*p!=',')
          HError(2660,"ParsePattern: missing , in itemlist"); 
       p++;
+      for (i=pList; i!=NULL; i=i->next) 
+         if (strcmp(((IPat *)i->item)->pat,buf)==0)
+            break;
+      if (i==NULL) {
       ip=(IPat*) New(&questHeap,sizeof(IPat));
       ip->pat = NewString(&questHeap,strlen(buf));
+         ip->index = nPatterns++;
       strcpy(ip->pat,buf);
-      ip->next = ipat; ipat = ip;
+         AddItem(NULL,ip,&pList);
+      }
+      else {
+         ip=(IPat *)i->item;
+      }
+      AddItem(NULL,ip,patList);
    } while (p<r);
    
-   return ipat;
+   return;
 }
 
 /* LoadQuestion: store given question in question list */
@@ -599,22 +620,22 @@
    }
    
    q=(Question *) New(&questHeap,sizeof(Question));
-   q->used=FALSE; q->qName=labid; q->patList = NULL;
+   q->used=FALSE; q->qName=labid; q->patList=NULL; q->index=nQuestions++;
    q->ilist = ilist;
    labid->aux=q; 
    strcpy(q->pattern, pattern);
    AddItem(NULL,q,&qList);
 
-   q->patList = ParsePattern(pattern);   
+   ParsePattern(&q->patList,pattern);   
 }
 
 /* IPatMatch: return true if given name matches pattern list */
-Boolean IPatMatch (char *name, IPat *patList)
+Boolean IPatMatch (char *name, ILink patList)
 {
-   IPat *ip;
+   ILink ip;
    
    for (ip=patList; ip!=NULL; ip=ip->next)
-      if (DoMatch(name,ip->pat)) return TRUE;
+      if (DoMatch(name, ((IPat *)(ip->item))->pat)) return TRUE;
    return FALSE;
 }
 
@@ -2768,7 +2787,7 @@
 
 typedef struct _Tree{           /* A tree */
    LabId baseId;                /* base phone name */
-   IPat *patList;               /* pattern list */
+   ILink patList;               /* pattern list */
    int state;                   /* state (or 0 if hmm tree) */
    int size;                    /* number of non terminal nodes */
    int nLeaves;                 /* number of terminal(leaf) nodes */
@@ -2824,7 +2843,7 @@
    /* pattern or baseId */ 
    if (usePattern) {
       strcpy(buf,baseId->name);
-      tree->patList = ParsePattern(buf);
+      ParsePattern(&tree->patList,buf);
    }
    tree->baseId = baseId;
    tree->state = state;
@@ -3198,25 +3216,119 @@
    return(prob);
 }
 
+/* SetQMTable: Set Question x Model bit table */
+void SetQMTable (void) 
+{
+   char *name,**PMTable;
+   int i,j,h;
+   MLink m;
+   ILink p,q;
+   Boolean answer;
+   IPat *ip;
+   Question *question;
+   Boolean **MTable;
+
+   const int size=(hset->numPhyHMM>>3)+1;
+
+   if (trace&T_BAS) {
+      printf("   setting question*model table...");
+      fflush(stdout);
+   }
+
+   /* set pattern * model table */
+   PMTable = (char **) New(&tmpHeap, nPatterns*sizeof(char *));
+
+   for (i=0; i<nPatterns; i++) {
+      PMTable[i] = (char *) New(&tmpHeap, size*sizeof(char));
+      memset(PMTable[i], 0, size);
+   }
+
+#pragma omp parallel for private(m,h,i,j,name,p,ip,answer)
+   for (h=0; h<MACHASHSIZE; h++) {
+      for (m=hset->mtab[h]; m!=NULL; m=m->next) {
+         if (m->type == 'h') {
+            /* index and name of current hmm */
+            i = ((HLink)(m->structure))->hIdx >> 3;  /* division by 8 */
+            j = ((HLink)(m->structure))->hIdx &  7;  /* residue by 8 */
+            name = m->id->name;
+
+            /* check answers */
+            for (p=pList; p!=NULL; p=p->next) {
+               ip = (IPat *)p->item;
+               answer = DoMatch(name, ip->pat);
+               if (answer)
+                  PMTable[ip->index][i] |= (1<<j);  /* set j-th bit */
+            }
+         }
+      }
+   }
+
+   /* set question * model table */
+   QMTable = (char **) New(&questHeap, nQuestions*sizeof(char *));
+   
+   for (i=0; i<nQuestions; i++) {
+      QMTable[i] = (char *) New(&questHeap, size*sizeof(char));
+      memset(QMTable[i], 0, size);
+   }
+
+#pragma omp parallel for private(h,i,j,q,question,p,ip)
+   for (h=0; h<hset->numPhyHMM; h++) {
+      i = h>>3;  j = h&7;
+      for (q=qList; q!=NULL; q=q->next) {
+         question = (Question *)q->item;
+         for (p=question->patList; p!=NULL; p=p->next) {
+            ip = (IPat *)p->item;
+            if (PMTable[ip->index][i] & (1<<j)) {
+               QMTable[question->index][i] |= (1<<j);  /* set j-th bit */
+               break;
+            }
+         }
+      }
+   }
+
+   /* free PMTable */
+   Dispose(&tmpHeap, PMTable);
+
+   if (trace&T_BAS) {
+      printf("done\n");
+      fflush(stdout);
+   }
+
+   setQMTable = TRUE;
+
+   return;
+}
+
 /* AnswerQuestion: set ans field in each cluster item in preparation for
    a possible split */
 Boolean AnswerQuestion(Node *node, Question *q)
 {
    CLink p;
    ILink i;
-   int yes=0, no=0;
-  
-   if (reduceMem) {
       MLink m;
+   int yes=0, no=0, index, j;
       
+   switch(reduceMem) {
+   case 2:
       for (p=node->clist;p!=NULL;p=p->next) {
          m = (MLink)p->item->owner->hook;
          p->ans = QMatch(m->id->name, q);
          if (p->ans) yes++;
          else        no++;
       }
+      break;
+   case 1:
+      index = q->index;
+      if (!setQMTable) SetQMTable();
+      for (p=node->clist; p!=NULL; p=p->next) {
+         j = p->item->owner->hIdx & 7;  /* residue by 8 */
+         p->ans = (QMTable[index][p->item->owner->hIdx>>3] & (1<<j)) ? TRUE : FALSE;
+         if (p->ans) yes++;
+         else        no++;
    }
-   else {
+      break;
+   case 0:
+   default: 
       /* set ans=FALSE for items in this cluster */
       for (p=node->clist;p!=NULL;p=p->next) {
       p->ans = FALSE;
@@ -3341,17 +3453,13 @@
    /* delete node->parent from leaves */
    p = node->parent;
    if (p!=NULL) {
-      if (p==tree->leaf) {
+      if (p==tree->leaf)
          tree->leaf = p->next;
-      }
-      if (p->prev!=NULL) {
+      if (p->prev!=NULL)
          p->prev->next = p->next;
-         p->prev = NULL;
-      }
-      if (p->next!=NULL) {
+      if (p->next!=NULL) 
          p->next->prev = p->prev;
-         p->next = NULL;
-   }
+      p->prev = p->next = NULL;
 }
 
    /* search insert location of given node */
@@ -4051,16 +4159,15 @@
 void PrintQuestions(FILE *file)
 {
    Question *q;
-   ILink i;
-   IPat *p;
+   ILink i,p;
   
    for (i=qList;i!=NULL;i=i->next) {
       q = (Question *)i->item;
       if (q->used) {
          fprintf(file,"QS %s ",q->qName->name);
-      fprintf(file,"{ %s",ReWriteString(q->patList->pat,NULL,DBL_QUOTE));
+         fprintf(file,"{ %s",ReWriteString(((IPat *)q->patList->item)->pat,NULL,DBL_QUOTE));
          for (p=q->patList->next;p!=NULL;p=p->next)
-         fprintf(file,",%s",ReWriteString(p->pat,NULL,DBL_QUOTE));
+            fprintf(file,",%s",ReWriteString(((IPat *)p->item)->pat,NULL,DBL_QUOTE));
       fprintf(file," }\n");
    }
    }
@@ -4221,7 +4328,7 @@
      if (s<=0 || s>hset->swidth[0])
        HError(9999,"LoadTree: stream index out of range");
      tree->streams.set[s] = TRUE;
-     p++;
+     while (*p!=',' && *p!=']') p++;
      while (*p==' ') p++;
 
      while (*p==',') {
@@ -4231,7 +4338,7 @@
            HError(9999,"LoadTree: stream index out of range");
         tree->streams.set[s] = TRUE;
         nStream++;
-        p++;
+        while (*p!=',' && *p!=']') p++;
         while (*p==' ') p++;
      }
      
@@ -4272,7 +4379,7 @@
             HError(-2661,"LoadTree: Macro %s not recognised",buf);
       }
       tree->nLeaves=1;
-      tree->root->id = GetLabId(buf, FALSE);
+      tree->root->id = GetLabId(buf, TRUE);
       tree->root->occ = GetNodeOcc(tree->root->macro[0],type);
    }
    else {
@@ -6244,7 +6350,7 @@
    ChkedAlpha("QS question name",qName);
    
    /* get copy of original item list whilst parsing it */
-   if (reduceMem) {
+   if (reduceMem!=0) {
       char pattern[PAT_LEN]; 
       ReadLine(&source, pattern);
       if (trace & T_QST) {
@@ -6252,6 +6358,7 @@
          fflush(stdout);
       }
       LoadQuestion(qName,NULL,pattern);
+      setQMTable=FALSE;
    }
    else {
       ILink ilist=NULL;
@@ -8200,7 +8302,7 @@
    char *pattern,*p;  /* pattern of items to use */
    int s;
 
-   ChkedAlpha("MMF file name", buf);
+   ChkedAlpha("JM MMF file name", buf);
 
    CreateHMMSet(&tmpSet,&hmmHeap,TRUE);
    tmpset = &tmpSet;
@@ -8221,7 +8323,10 @@
    ClearSet(streams);
    pattern = PItemList(&ilist,&type,tmpset,&source,&streams,0,0,(trace&T_ITM)?TRUE:FALSE);
 
+   if (trace&T_BID) {
    printf("JM %s %s\n", buf, pattern);
+      fflush(stdout);
+   }
 
    /* extract specified model pattern */
    if (type!='h') {

References
[hts-users:01875] Re: Fast & memory efficient HHEd clustering patch, Heiga Zen (Byung Ha CHUN)